Целочисленный двоичный поиск

Определение:

Целочисленный двоичный поиск (бин. поиск) — алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку.

Формулировка задачи

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

Принцип работы

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

Правосторонний/левосторонний целочисленный двоичный поиск

Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения [math] x [/math] .

Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения [math] x [/math] .

Это разделение помогает находить количество подряд идущих равных значений.

Например:
Задан отсортированный массив [math][1, 2, 2, 2, 2, 3, 5, 8, 9, 11][/math]

Правосторонний поиск двойки выдаст в результате [math]5[/math], в то время как левосторонний выдаст [math]2[/math].

От сюда следует, что количество подряд идущих двоек равно длине отрезка [math][2;5][/math], то есть [math]4[/math].

Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.

Алгоритм двоичного поиска

Схема бин. поиска

Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым. В случае равенства возвращать его, а если искомое больше(в случае правостороннего — не меньше), чем элемент сравнения, то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на [math]1[/math], или же пока мы не найдём искомый индекс.

Код

binSearch(l, r)               // l, r - левая и правая границы
  while l < r - 1             // запускаем цикл
    m = (l + r) / 2;          // m - середина области поиска
    if a[m] ⩽ k
      l = m; 
    else 
      r = m;                  // сужение границ

В случае правостороннего поиска изменится знак сравнения при сужении границ на ([math]a[m] \leqslant k[/math]).

Инвариант цикла: пусть левый индекс меньше или равен искомого элемента, а правый — строго больше, тогда если [math]l = r - 1[/math], то понятно, что [math]l[/math] — самое правое вхождение (так как следующее уже больше).

Источники

• Д. Кнут - Искусство программирования (Том 3, 2-е издание)

Ссылки

Википедия - двоичный поиск