Основы программирования

Бинарный поиск


Пусть можно сравнивать элементы множества друг с другом, определяя, какой из них больше. (Например, для текстовых строк применяется лексикографическое сравнение: первые буквы сравниваются по алфавиту; если они равны, то сравниваются вторые буквы и т.д.) Тогда можно существенно убыстрить поиск, применяя алгоритм бинарного поиска. Для этого элементы множества хранятся в массиве в возрастающем порядке. Идея бинарного поиска иллюстрируется следующей шуточной задачей: : "Как поймать льва в пустыне? Надо разделить пустыню забором пополам, затем ту половину, в которой находится лев, снова разделить пополам и так далее, пока лев не окажется пойманным".

В алгоритме бинарного поиска мы на каждом шагу делим отрезок массива, в котором может находиться искомый элемент x, пополам. Рассматриваем элемент y в середине отрезка. Если x меньше y, то выбираем левую половину отрезка, если больше, то правую. Таким образом, на каждом шаге размер отрезка массива, в котором может находиться элемент x, уменьшается в два раза. Поиск заканчивается, когда размер отрезка массива (т.е. расстояние между его правым и левым концами) становится равным единице, т.е. через [log2n]+1 шагов, где n — размер массива. В нашем примере это произойдет после 20 шагов (т.к. log21000000 < 20). Таким образом, вместо миллиона операций сравнения при последовательном поиска нужно выполнить всего лишь 20 операций при бинарном.

Запишем алгоритм бинарного поиска на псевдокоде. Дан упорядоченный массив a вещественных чисел (вещественные числа используются для определенности; бинарный поиск можно применять, если на элементах множества определен линейный порядок, т.е. для любых двух элементов можно проверить их равенство или определить, какой их них больше). Пусть текущее число элементов равно n. Элементы массива упорядочены по возрастанию:

a[0] < a[1] < · ·· < a[n - 1]

Мы ищем элемент x. Требуется определить, содержится ли x в массиве. Если элемент x содержится в массиве, то надо определить индекс i ячейки массива, содержащей x:


найти i: a[i] = x

Если же x не содержится в массиве, то надо определить индекс x, такой, что при добавлении элемента x в i-ю ячейку массива элементы массива останутся упорядоченными, т.е.

найти i: a[i-1] < x =< a[i]

(считается, что a[-1] = -?, a[n] = + ?). Объединив оба случая, получим неравенство

a[i-1] < x =< a[i]

Используем схему построения цикла с помощью инварианта. В процессе выполнения хранятся два индекса b и e (от слов begin и end), такие, что

a[b] < x =< a[e]

Индексы b и e ограничивают текущий отрезок массива, в котором осуществляется поиск. Приведенное неравенство является инвариантом цикла. Перед началом выполнения цикла рассматриваются разные исключительные случаи — когда массив пустой (n=0), когда x не превышает минимального элемента массива (x =< a[0]) и когда x больше максимального элемента (x > a[n-1]). В общем случае выполняется неравенство

a[0] < x =< a[n-1])

Полагая b = 0, e = n - 1, мы обеспечиваем выполнение инварианта цикла перед началом выполнения цикла. Условие завершения состоит в том, что длина участка массива, внутри которого может находится элемент x, равна единице:

b - e = 1

В этом случае

a[e-1] < x =< a[e]

т.е. искомый индекс i равен e, а элемент x содержится в массиве тогда и только тогда, когда x = a[e]. В цикле мы вычисляем середину c отрезка [b,e]

с = целая часть ((b+e)/2)

и выбираем ту из двух половин [b,c] или [c,e], которая содержит x. Для этого достаточно сравнить x со значением a[c] в середине отрезка. Завершение цикла обеспечивается тем, что величина e - b монотонно убывает после каждой итерации цикла.

Приведем текст алгоритма бинарного поиска:

лог алгоритм бинарный_поиск( вход: цел n, вещ a[n], вещ x, выход: цел i ) | Дано: n — число элементов в массиве a, | a[0] < a[1] < ... < a[n-1] | Надо: ответ := (x содержится в массиве), | вычислить i, такое, что | a[i-1] < x <= a[i] | (считая a[-1] = -беск., a[n] = +беск.) начало | цел b, e, c; | | // Рассматриваем сначала исключительные случаи | если (n == 0) | | то i = 0; | | ответ := ложь; | иначе если (x <= a[0]) | | i := 0; | | ответ := (x == a[0]); | иначе если (x > a[n-1]) | | i := n | | ответ := ложь; | иначе | | // Общий случай | | утверждение: a[0] < x <= a[n-1]; | | b := 0; e := n-1; | | | | цикл пока e - b > 1 | | | инвариант: a[b] < x и x <= a[e]; | | | c := целая часть((b + e) / 2); | | | если x <= a[c] | | | | то e := c; | | | иначе | | | | b := c; | | | конец если | | конец цикла | | | | утверждение: e - b == 1 и | | a[b] < x <= a[e]; | | i := e; | | ответ := (x == a[i]); | конец если конец алгоритма


Содержание раздела