Метод двух указателей и бинарный поиск
Метод двух указателей
Рекомендуемые источники
Видеозапись А.С.Куликова про два указателя
Краткая теория про два указателя
Слияние двух отсортированных массивов и merge-sort
Примеры задач
Бинарный поиск
Вводная
Что если у вас есть некоторый набор данных, будь-то чисел или список имен и вы хотите быстро научиться отвечать на запрос “есть ли среди вашего набора такой-то элемент”?
В таком случае можно как в телефонном справочнике упорядочить все записи в порядке возрастания (или если речь идет про список имен - то в алфавитном порядке), и затем когда приходит запрос “есть ли 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) Если ваша программа работает очень долго на простом тесте, то вероятно она зависла, а точнее - цикл сужения диапазона поиска от раза к разу работает с одним и тем же диапазоном, т.е. диапазон перестал уменьшаться, и т.о. весь алгоритм обречен на вечные поиски.
Что тогда делать? То же что предложено выше - отладьте вашу программу. Посмотрите почему она сошлась в этот диапазон поиска, и почему он на очередной итерации не сужается а остается таким же. Вы можете это исследовать как выводя все важные переменные в консоль, так и воспользовавшись отладчиком.