Не забудьте принести летнее задание на следующий урок.

Вводная

Что если у вас есть некоторый набор данных, будь-то чисел или список имен и вы хотите быстро научиться отвечать на запрос “есть ли среди вашего набора такой-то элемент”?

В таком случае можно как в телефонном справочнике упорядочить все записи в порядке возрастания (или если речь идет про список имен - то в алфавитном порядке), и затем когда приходит запрос “есть ли X”, то достаточно:

0) Пусть в массиве \(as[i]\) содержится \(N\) элементов в порядке возрастания и нужно найти элемент \(x\).

1) Изначально ответ находится в диапазоне поиска с элемента под индексом \(left=0\) до \(right=N-1\) (т.е. весь массив).

2) Посмотрим в элемент в середине диапазоне поиска, т.е. на элемент по индексу \(medium=(left+right)/2\).

3.1) Если элемент в середине меньше искомого (т.е. \(as[medium] \leq X\)), то продолжать искать надо в правой половине, т.е. левая граница сдвинулась в центр, т.е. теперь \(left=medium\).

3.2) Иначе продолжать искать надо в левой половине, т.е. правая граница сдвинулась в центр, т.е. теперь \(right=medium\).

4) Если ответ еще не найден - продолжаем смотря на элемент в середине диапазона постепенно его сужать, т.е. вновь продолжаем шаги 2-4.

Определения

Правосторонний поиск - поиск такого наибольшего (т.е. самого правого) индекса \(i\) что \(as[i] \leq x\), где \(x\) - искомый элемент.

Левосторонний поиск - поиск такого наименьшего (т.е. самого левого) индекса \(i\) что \(as[i] \geq x\), где \(x\) - искомый элемент.

Алгоритм

Псевдокод для левостороннего поиска рекомендуется посмотреть здесь - ИТМО вики-конспекты: Целочисленный двоичный поиск.

Обратите внимание что чтобы изменить левосторонний поиск на правосторонний достаточно поправить две вещи: знак сравнения элемента в середине с искомым и то какой индекс является ответом и возвращается в самом конце.

Советы

1) Подготовьте несколько простых тестов, затем отладьте вашу программу посмотрев как меняется диапазон поиска:

  • Выводя его через System.out.println("left=" + l + ", right=" + r);
  • Отлаживая по шагам как было рассказано раньше

2) Если ваша программа работает очень долго на простом тесте, то вероятно она зависла, а точнее - цикл сужения диапазона поиска от раза к разу работает с одним и тем же диапазоном, т.е. диапазон перестал уменьшаться, и т.о. весь алгоритм обречен на вечные поиски.

Что тогда делать? То же что предложено выше - отладьте вашу программу. Посмотрите почему она сошлась в этот диапазон поиска, и почему он на очередной итерации не сужается а остается таким же. Вы можете это исследовать как выводя все важные переменные в консоль, так и воспользовавшись отладчиком.