§ 65. Двоичный поиск

Определения и обозначения

Двоичный поиск — способ найти элемент в упорядоченной последовательности, каждый раз отбрасывая половину оставшегося диапазона. В отличие от проверки элементов подряд, алгоритм сразу исключает много кандидатов. Это помогает быстро искать значения в больших массивах.

Упорядоченная последовательность — последовательность, элементы которой расположены по возрастанию или убыванию. Это обязательное условие двоичного поиска: только порядок позволяет определить, где может находиться искомое значение. Без него нельзя безопасно отбросить половину элементов.

Середина диапазона — элемент, с которым на каждом шаге сравнивают искомое значение, чтобы выбрать одну из половин для дальнейшего поиска. Например, если массив возрастающий и искомое число меньше значения в середине, искать нужно слева. Проверка середины определяет направление следующего шага.

Границы поиска — индексы начала и конца той части последовательности, где ещё может находиться искомый элемент. Сначала они охватывают весь массив, затем сдвигаются после каждого сравнения. По границам понятно, какие индексы ещё не исключены и завершился ли поиск.

Как это устроено

Сначала диапазоном поиска делают весь массив: его границы показывают, что пока возможен любой индекс. Затем находят середину и сравнивают её значение с искомым. Это сравнение полезно потому, что упорядоченность сообщает, по какую сторону от середины могут быть подходящие элементы.

Если значения совпали, найденный элемент уже проверен, поэтому алгоритм может остановиться. Если массив расположен по возрастанию и искомое значение меньше среднего, справа от середины находятся только не меньшие значения; значит, там искать незачем. Если оно больше среднего, исключают левую часть по той же причине.

После выбора половины её границы становятся новыми границами поиска. Проверенный средний элемент тоже исключают, если он не совпал: повторная проверка не даст новой информации. Так диапазон уменьшается примерно вдвое на каждом шаге, а не на один элемент, как при обычном последовательном просмотре.

Алгоритм продолжают, пока значение не найдено или диапазон не опустел. В первом случае ответом служит индекс совпавшего элемента. Во втором левая граница оказывается правее правой, то есть ни одного допустимого индекса больше нет; это доказывает, что искомое значение отсутствует.

Если в массиве n элементов, двоичному поиску в худшем случае требуется порядка log₂ n сравнений, потому что число возможных элементов каждый раз делится примерно пополам. Например, для тысячи элементов достаточно около десяти шагов, тогда как линейный поиск может проверить все тысячу. Однако двоичный поиск выгоден лишь при готовом упорядоченном массиве: подготовка данных сортировкой тоже требует времени.

Свойства линейного и двоичного поиска

Таблица помогает выбрать способ поиска с учётом состояния данных и размера массива. Если порядок не задан, линейный поиск надёжнее, а сортировка ради одного поиска может не окупиться. Для большого отсортированного массива обычно выгоднее двоичный метод.

Разбор задач

Поиск числа 16

В массиве [2, 5, 8, 12, 16, 23, 38] нужно найти 16 и записать проверяемые элементы. Индексы массива идут от 0 до 6, поэтому сначала середина имеет индекс 3. После каждого сравнения оставляем только ту часть, где число 16 ещё может находиться.

1. Проверяем элемент с индексом 3: это 12. Поскольку 16 больше 12, в возрастающем массиве оставляем правую часть.
2. В диапазоне индексов от 4 до 6 середина имеет индекс 5, элемент равен 23. Число 16 меньше 23, поэтому оставляем левую часть диапазона.
3. Теперь обе границы равны 4. Проверяем элемент 16 и получаем совпадение, значит, поиск завершён.

Проверенные элементы: 12, 23, 16. Ответ: число найдено по индексу 4.

Поиск отсутствующего числа в массиве из 1000 элементов

Точное значение искомого числа не задано, поэтому нельзя назвать конкретные элементы массива, которые будут проверены. Но можно определить ход поиска: каждый раз середина делит текущий отрезок индексов, а сравнение указывает, в какую часть двигаться. Поскольку число отсутствует, совпадения не будет, и в конце все возможные индексы исключатся.

1. Начинаем с границ 0 и 999. Проверяем элемент с индексом 499; по результату сравнения выбираем левую или правую часть.
2. Для оставшейся части снова берём середину и сравниваем её с искомым значением. После каждого шага проверяем только одну из половин, отбрасывая другую.
3. Повторяем сокращение диапазона, пока границы не пересекутся: левая граница станет больше правой. Пустой диапазон означает, что ни один индекс не подходит.

Ответ: число отсутствует. Конкретная последовательность проверяемых значений зависит от того, где оно должно было бы находиться относительно элементов массива.

Массив из 1024 элементов

Нужно оценить максимальное число сравнений двоичного поиска и сопоставить его с линейным. При каждом шаге число кандидатов сокращается примерно вдвое, а 1024 = 2¹⁰. Поэтому после десяти делений от исходного диапазона остаётся единичный кандидат, который при необходимости проверяют.

1. Записываем размер как степень двойки: 1024 = 2¹⁰.
2. Деление пополам повторяем около десяти раз, следовательно, двоичный поиск требует примерно 10 сравнений.
3. Линейный поиск в худшем случае проверит каждый элемент — до 1024 сравнений. При отсутствии значения он тоже может дойти до конца массива.

Ответ: для двоичного поиска оценка составляет около 10 сравнений, для линейного — до 1024. Точное число для двоичного метода зависит от принятого варианта выбора середины и от того, найдено ли значение.

Типичные ошибки

• Искать в неупорядоченном массиве. Так поступают, забыв, что половину можно отбросить только при известном порядке значений. Самопроверка: убедитесь, что соседние элементы расположены по возрастанию или убыванию.
• Неверно обновлять границы. Если оставить проверенную середину или сдвинуть границу не в ту сторону, диапазон может не уменьшаться либо нужный индекс будет потерян. Проверяйте, что новый диапазон содержит все ещё возможные индексы и становится меньше предыдущего.
• Не сравнивать искомое значение с серединой до сужения диапазона. Ошибка возникает, когда сразу выбирают половину, не проверив, не найден ли ответ. Сначала сравните значения; при совпадении остановитесь, иначе исключайте проверенный индекс.
• Считать двоичный поиск всегда более быстрым. Его преимущество может быть небольшим на короткой последовательности или исчезнуть, если данные сначала нужно сортировать. Сравните затраты на подготовку данных и число поисков, а не только число шагов одного запуска.

Связь с другими темами

Для понимания двоичного поиска нужны понятия массива и индекса: границы обозначают номера элементов, которые ещё могут подойти. Также необходимо уметь сравнивать значения и понимать, что значит расположить последовательность по порядку. Без этих знаний нельзя выбрать середину и определить сторону поиска.

Метод применяется при работе с отсортированными данными, например в больших массивах. Он также помогает изучать сложность алгоритмов: на его примере видно, как деление задачи пополам приводит к логарифмическому росту числа сравнений. Это позволяет сравнивать эффективность разных способов решения.

Что запомнить

• Двоичный поиск применяют к упорядоченной последовательности.
• На каждом шаге искомое значение сравнивают с элементом в середине диапазона.
• После сравнения сохраняют только ту половину, где ещё может быть искомый элемент.
• Поиск завершается при нахождении элемента или опустошении диапазона.
• Число сравнений растёт логарифмически с длиной последовательности.
• Корректное обновление границ необходимо, чтобы алгоритм завершался и не пропускал элементы.