Перед первой итерацией определяется средний элемент в данном списке. При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка.
Когда целевое значение меньше среднего элемента, то можно сделать вывод, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента и оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка.
Таким образом, повторяя раз за разом данное деление списка по пополам, будет либо обнаружен искомый элемент, либо будет ясно, что он отсутствует.
1.2.1 Блок-схема алгоритма бинарного поиска
1.2.2 Анализ сложности алгоритма
Анализ наихудшего случая.
При каждом делении списка пополам, то есть с каждой итерацией цикла, степень двойки в длине оставшейся части списка уменьшится на 1, а также. Когда происходит последняя итерация цикла, размер оставшейся части становится равным 1, а это происходит при k=1 (так как 21 -1=1). Это означает, что при N=2k -1 число проходов не превышает k. Решая последние уравнение относительно k выходит, что в наихудшем случае число проходов равно k=log2 (N+1).
Анализ среднего случая.
В среднем случае сложность можно оценить, используя ту же схему рассмотрения, но находя среднее число итераций по всем элементам массива.
в общем виде отличается от формулы не более, чем на 0,5.
Таким образом, алгоритм обладает логарифмической временной сложностью по данным.
