Анализ алгоритма бинарного поиска

Порядок функции ВС алгоритма бинарного поиска равен O(log ₂ N). Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более log ₂ N таких уменьшений, т.е. выполняется не более log ₂ N шагов алгоритма. В лучшем случае, когда искомый элемент находится в середине массива, число сравнений не зависит от количества элементов в массиве и порядок функции ВС будет O(1).

Определим среднее число шагов при поиске элементов в массиве из N элементов. Для этого подсчитаем суммарное число шагов S при поиске каждого элемента массива. Исходя из алгоритма, не более чем N / 2 элементов ищется за log ₂ N шагов, N / 4 элементов — за (log ₂ N) – 1 шагов, и т.д. Отсюда .

Среднее число шагов равно S / N, что составляет O(log ₂ N).