Поиск делением пополам (двоичный поиск).
Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Вообразите себе телефонный справочник, в котором фамилии не будут расположены по порядку. Это нечто совершенно бесполезное! Поэтому мы приводим алгоритм, основанный на знании того, что массив а упорядочен, т.е. удовлетворяет условию
Ak : 1£ k < N : ak-1 ¹ ak
Основная идея - выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Это соображение приводит нас к следующему алгоритму (он называется "поиском делением пополам"). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.
L := 0;
R := N-1;
found := FALSE;
WHILE (L Ј R) AND NOT found DO
m := любое значение между L и R;
IF a[m] = x THEN found := TRUE;
IF a[m] < x THEN L := m+1
ELSE R := m-1;
END;
END;
Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:
(L £ R) AND (Ak
: 0 £ k < L : ak < x) AND (Ak
: R < k < N : ak > x)
из чего выводится результат
found OR ((L > R) AND (Ak : 0 £ k < L : ak
< x) AND (Ak : R < k < N : ak > x))
откуда следует
(am = x) OR (Ak : 0 £ k < N : ak ¹ x)
Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива.
В результате максимальное число сравнений равно log N, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N/2.
Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log N. Быстрый алгоритм основан на следующем инварианте:
(Ak : 0 £ k < L : ak < x) AND (Ak : R £ k < N : ak ³ x)
причем поиск продолжается до тех пор, пока обе секции не "накроют" массив целиком.
L := 0;
R := N;
WHILE L < R DO
m := (L+R) DIV 2;
IF a[k] < x THEN L := m+1
ELSE R := m ;
END
END
Условие окончания - L і R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R-L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L Ј m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m+1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а[R] в сравнениях никогда не участвует.Следовательно, необходима дополнительная проверка на равенство а[R] = x. В отличие от первого нашего решения приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.
