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

Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Поэтому мы приводим алгоритм, осно¬ванный на знании того, что массив A упорядочен, т. е. удовлетворяет условию: A_k:1≤k<N:a_k-1≤a_k.

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

L=0; R=N-1; ff=0;
while ((L<=R)&&(ff!=1) {
/* m – любое значение между L и R */
if (a[m]=x) ff=1;
else if (a[m] else R=m-1;
};
Инвариант цикла, т. е. условие, выполняющееся перед каждым шагом, таков:
(L≤R) &(A_k: 0≤k<L: a_k<x)
&(A_k: R<k<N: a_k>x),
из чего выводится результат:
found OR ((L > R) &(A_k: 0≤k<L: a_k<x) &(A_k: R<k<N:a_k>x)),
откуда следует:
(a_m= x) OR (A_k: О ≤ k<N: a_k!=x).

Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность влияет выбор m. Ясно, что наша задача — исключить на каждом шаге из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log N, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений N/2.

Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она удовлетворяется лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания закончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако, при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае — log N. Быстрый алгоритм основан на следующем инварианте: (A_k : 0 < k < =L: а_k < х) & (A_k : R ≤ k < N: a_k >= х), причем поиск продолжается до тех пор, пока обе секции не "накроют" массив целиком.
L=0; R=N;
while (L m=(L+R)/2;
if (a[m]<x) L=m+1;
else R=m;
}; /p>

Условие окончания — L >= R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R - L на каждом шаге убывает. В начале каждого шага L< R. Для среднего арифметического m справедливо условие L < m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m + 1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент a[R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство a[R] = х. В отличие от первого нашего решения, приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.