Поиск делением пополам (двоичный поиск)

Линейный поиск

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

1. Элемент найден, т. е. а_i=х.
2. Весь массив просмотрен и совпадения не обнаружено.

Это дает нам линейный алгоритм:

i:=1;

WHILE (i<=N) and (a[ i ] <> x) DO i:=i+1; (1.36)

Обратите внимание, что порядок элементов в логиче­ском выражении имеет существенное значение. Инва­риант цикла, т. е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:

(1 ≤ i≤ N) & (A k: 1 ≤ k < i: a_k ≠ x) (1.37)

Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что по­иск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие:

((i = N+1) OR (а_i = х)) & (A k: 1 ≤ k < i: a_k ≠ х)

Это условие не только указывает на желаемый ре­зультат, но из него же следует, что если элемент най­ден, то он найден вместе с минимально возможным индексом, т. е. это первый из таких элементов. Равен­ство i = N+1 свидетельствует, что совпадения не суще­ствует.

Совершенно очевидно, что окончание цикла гаран­тировано, поскольку на каждом шаге значение i уве­личивается, и, следовательно, оно, конечно же, до­стигнет за конечное число шагов предела N+1; факти­чески же, если совпадения не было, это произойдет после N+1 шагов.

Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыст­рить поиск? Единственная возможность — попытаться упростить само логическое выражение, ведь оно со­стоит из двух членов. Следовательно, единственный шанс на пути к более простому решению—сформу­лировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого доста­точно в конец массива поместить дополнительный элемент со значением х. Назовем такой вспомога­тельный элемент «барьером», ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так: a: ARRAY [ 1..N+1 ] OF INTEGER и алгоритм линейного поиска с барьером выглядит следующим образом:

i:=1; a[ N+1 ]:=x;

WHILE (a[ i ] <> x) DO i:=i+1; (1.38)

Результирующее условие, выведенное из того же ин­варианта, что и прежде:

(а_i = х)) & (A k: 1 ≤ k < i: a_k ≠ х)

Ясно, что равенство i = N+1 свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

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

A k: 1 ≤ k ≤ N: a_k-1 ≤ a_k (1.39)

Основная идея—выбрать случайно некоторый эле­мент, предположим a_m, и сравнить его с аргументом поиска х. Если он равен х, то поиск заканчивается, если он меньше х, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно ис­ключить из дальнейшего поиска; если же он больше х, то исключаются индексы больше и равные т. Это соображение приводит нас к следующему алгоритму (он называется «поиском делением пополам»). Здесь две индексные переменные L и R отмечают соответ­ственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.

L:=1; R:=N; found:=FALSE; (1.40)

WHILE (L<=R) and NOT found DO

Дата добавления: 2014-01-13