Основная идея бинарного поиска довольно проста, но детали нетривиальны, и правильно написать работающий алгоритм удается далеко не с первого раза. В одной из наиболее популярных реализаций этого алгоритма используется два указателя (l и u), соответствующие нижней и верхней границам поиска. С помощью этого алгоритма ищется элемент k в упорядоченном по возрастанию массиве a, содержащем n элементов.
1. Начальная установка l = 1, u = n.
2. Если u < l, то алгоритм окончен неудачно, иначе найти середину интервала [l; u]. В этот момент мы знаем, что если k есть в массиве, то выполняются неравенства a_l ≥ k ≥ a_u. Установить i = [( l + u ) / 2]. Теперь i указывает примерно на середину рассматриваемой части массива.
3. Если k < a_i, то перейти к шагу 4, если k > a_i, то перейти к шагу 5, если k = a_i, алгоритм окончен удачно.
4. Установить u = i – 1 и перейти к шагу 2.
5. Установить l = i + 1 и перейти к шагу 2.
Шаг 3 алгоритма бинарного поиска выполняется порядка log₂ n раз, то есть данный алгоритм имеет логарифмическую сложность по числу сравнений.