singlepost

Двоичный поиск в двумерном массиве на QBasic << На главную или назад  

Помогите с реализацией программы двоичного поиска в упорядоченном по возрастанию массиве NxM.

9 ответов в теме “Двоичный поиск в двумерном массиве на QBasic”

  1. 7
    Константин Конашенков ответил:

    Ну.. это было мое мнение )
    Бинарный поиск предполагает деление пространства поиска на 2, и мой вариант больше подхъодит

  2. 6
    Глеб Паскевич ответил:

    Вообще, логично было бы искать число в каждом ряду методом "двоичного поиска" TM и всё. Правда, там ограничение на кол-во операций.

  3. 5
    Константин Конашенков ответил:

    а тут я думаю стоит расмматривать ряды как элементы. Берем находим середину(строку,в вашем случае три элемента), в ней проверяем есть ли элемент, а далее последний элемент предыдущей строки и первый элемент следующей.

  4. 4
    Глеб Паскевич ответил:

    Просто массив может быть вида
    1 1 2
    2 3 3
    3 4 5
    3 5 9
    5 6 10

    И ищем число 3. И 3 с обеих сторон.

  5. 3
    Константин Конашенков ответил:

    В алгоритмах не очень , но деля на 2 мы получаем границу, и смотрим что слева, что справа. Могу предположить, что есть допущение, что искомое число одно.

    //ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B...
    Пробежал глазами алгоритм, из него я делаю вывод, что число все таки 1.

    Плюс мона посмотреть и под другим углом, если элементов много, нам не говориться какой именно найти (вернуть индекс ;)

  6. 2
    Глеб Паскевич ответил:

    Ошибочка. Неубывающий массив. Просто число может оказаться в обоих частях.

  7. 1
    Константин Конашенков ответил:

    и ? Все просто у тебя есть что искать. У тебя есть где искать, бинарный поиск предполагает деление промежутка пополам, а затем проверка в какой части в первой или второй (а у тебя отсортировано) находится искомая цель поиска. Поэтому это и называется бинарный/двоичный, потому что каждый раз область поиска уменьшается в 2 раза

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.