Алгоритм бинарного поиска
Одной из важнейших задач программирования и информатики в целом является задача поиска какого-либо элемента в наборе. Это может быть поиск пользователя в базе данных, поиск друзей конкретного человека в социальной сети и т.д.
Рассмотрим алгоритм поиска на примере задачи проверки наличия числа в некоторой последовательности. Например, пусть имеется следующая последовательность чисел:
Пусть необходимо проверить, находится ли число -3 в последовательности. Интуитивно мы понимаем, что для того, чтобы обнаружить то или иное число в последовательности придется просмотреть всю последовательность, пока мы не встретим искомое. Таким образом, для действительно длинных наборов такой поиск будет выполняться достаточно долго — при увеличении длины последовательности в два раза, поиск также займет в 2 раза больше времени.
Что может помочь нам ускорить время поиска элемента в наборе?
Вспомним, какая стратегия лучше всего подойдет для поиска какого-либо слова в словаре. Учитывая то, что все слова в словаре расположены в лексикографическом (по алфавиту) порядке, для начала мы можем открыть словарь на произвольной странице (например, на середине). Далее, если мы не обнаружили искомого слова на странице, мы принимаем решение искать его либо в левой, либо в правой половине. Процесс продолжаем до тех пор, пока не обнаружим нужного слова.
Аналогичная идея заложена в алгоритме бинарного поиска, предполагающего предварительную упорядоченность данных.
Рассмотрим алгоритм бинарного поиска на примере задачи, описанной в начале статьи. Для начала пронумеруем все элементы последовательности:
Теперь упорядочим элементы по возрастанию и определим, какой элемент является центральным. Все элементы слева от центра — левая сторона последовательности, справа от центра — правая сторона последовательности.
Заметим, что все элементы левой последовательности меньше центра и меньше всех элементов из правой последовательности. Последние, в свою очередь больше центра и всех элементов левой последовательности.
Очевидно, что в результате сравнения искомого числа и центрального элемента, число -3 оказалось меньше числа 5, следовательно искомое число -3 расположено в левой части.
Теперь выполним разделение левой части набора чисел аналогичным образом. Так как сейчас последовательность имеет четную длину, мы не можем строго определить центральный элемент. Положим, что центр — элемент, расположенный левее относительно мнимого центра.
Теперь центральным элементом является число 0. Следовательно, в результате сравнения получаем, что отрицательное число -3 находится в левой стороне последовательности относительно нового центра 0. Поскольку в левой части последовательности остался только один элемент, равный искомому, поиск успешно завершен — элемент найден.
Опишем алгоритм бинарного поиска в более формальном виде:
1) Выполняем сортировку последовательности.
2) Сравниваем искомый элемент с элементом, расположенным в середине последовательности.
3) Поиск элемента продолжается в левой части последовательности, если он меньше центрального, и в правой — если больше центрального.
4) Вычисляется новый центральный элемент в левой или правой стороне.
5) Процесс 2-4 повторяется, пока не будет найден центральный элемент, совпадающий с искомым, или область для поиска станет пустой.
В данной статье мы рассмотрели алгоритм бинарного поиска.
Зачастую, на собеседовании задают большое количество вопросов по алгоритмам и структурам данных. Также большинство задач, решаемых программистами в настоящее время требуют хорошего понимания работы тех или иных алгоритмов. В частности, большое внимание уделяется:
1) Общему принципу работы алгоритма.
2) Его асимптотической сложности.
3) Его применимости к различным входным данным.
Также один из важнейших компонентов Java — Java Collection API — базируется на применении огромного числа алгоритмов поиска, сортировки и распределения данных, понимание которых необходимо разработчику для их эффективного использования.
Марсель Сидиков @it.drive