Двоичный поиск (поиск делением пополам, бинарный поиск)

 

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

Основная идея – выбрать случайным образом некоторый элемент, предположим, a [ m ], и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается; если больше, то искать x следует в левой от a [ m ] части массива; если элемент a [ m ] меньше x, то искать x следует в правой от a [ m ] части массива. Эта идея приводит нас к алгоритму, называемому “ поиск делением пополам ”или“ двоичный (бинарный) поиск ”. В приведенном ниже алгоритме две индексные переменные L и R отмечают соответственно левый и правый конец части массива, где еще может быть обнаружен аргумент поиска x.

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

1. Определим L и R как левую и правую границу интервала поиска соответственно.

2. Выберем произвольное m, лежащее между L и R, т.е. L m R.

3. Сравним x с элементом массива a [ m ]; если они равны, то алгоритм завершен, иначе выполняем шаг 4.

4. Если x > a [ m ], то изменяем левую границу интервала: L = m +1, иначе изменяем правую границу интервала: R = m –1.

5. Если интервал не пуст, т.е. L R, идем на шаг 2.

 

Выбор m произволен в том смысле, что корректность алгоритма от него не зависит. Однако, выбор m влияет на эффективность алгоритма. Наша задача – исключить из дальнейшего поиска как можно больше элементов, независимо от результата сравнения. Оптимальным решением будет выбор среднего элемента, т.к. при этом в любом случае будет исключаться половина интервала.

Приведем примеры работы алгоритма при положительном и отрицательном результате поиска. В массиве

a [10]: 01 05 09 11 16 17 20 24 34 38

будем искать элемент x = 34.

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

 

L = 0, R = 9, m = (0 + 9) / 2 = 9 / 2 = 4

 

L				m					R

 

L = 5, R = 9, m = (5 + 9) / 2 = 14 / 2 = 7

 

					L		m		R

L = 8, R = 9, m = (8 + 9) / 2 = 17 / 2 = 8

 

								L=m	R

 

Результат поиска положителен. Искомое число обнаружено на девятом месте. Теперь в этом же массиве поищем элемент x = 02.

 

L = 0, R = 9, m = (0 + 9) / 2 = 9 / 2 = 4

 

L				m					R

L = 0, R = 3, m = (0 + 3) / 2 = 3 / 2 = 1

 

L	m		R

 

L = 0, R = 0, m = (0 + 0) / 2 = 0 / 2 = 0

 

L=m=R

 

Здесь L стало равно 1, R осталось равным 0, т.е. L > R, а, следовательно, искомого числа нет в данном массиве.

Блок-схема бинарного поиска.

 

Переменная flag изменяет свое значение (с 0 на 1), если аргумент поиска найден.

 

 

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

В этом случае цикл заканчивается, как только выполнится условие: L R. Но окончание цикла ничего не говорит о наличии или отсутствии аргумента поиска x в массиве (заметим, что после выхода из цикла L = R = m). Конечно, при R = N никаких совпадений нет, так как в этом случае происходит выход за границу массива. В других же случаях необходима дополнительная проверка на равенство a [ m ] = x. Кроме того, надо обратить внимание на изменение границ интервала при изменении условий цикла.

Результатом приведенных выше рассуждений является следующая блок-схема.

 

 

Проверим истинность наших рассуждений на предыдущем примере. Напомним, в массиве

a [10]: 01 05 09 11 16 17 20 24 34 38

мы ищем элемент x = 34

 

L = 0, R = 9, m = (0 + 9) / 2 = 9 / 2 = 4

 

L				m					R

L = 5, R = 9, m = (5 + 9) / 2 = 14 / 2 = 7

 

					L		m		R

L = 8, R = 9, m = (8 + 9) / 2 = 17 / 2 = 8

 

								L=m	R

L = 8, R = 8, m = (8 + 8) / 2 = 16 / 2 = 8

 

							L=m = R

 

Результат поиска положителен. Искомое число обнаружено на девятом месте.

 

 

Поиск подстроки в строке.

 

Часто приходится сталкиваться со специфическим поиском, так называемом поиском подстроки в строке. Его можно определить следующим образом. Пусть задана строка S из N элементов и строка p из M элементов. Описаны они так:

string S [ N ], P [ M ];

Задача поиска подстроки P в строке S заключается в нахождении первого слева вхождения P в S, т.е. найти значение индекса i, начиная с которого

S [ i ] = P [0], S [ i + 1] = P [1],…, S [ i + M – 1] = P [ M – 1].

 

1.2.1. Прямой поиск подстроки в строке.

 

Разберем самый очевидный, самый “прямолинейный” алгоритм поиска.