O(n). Бинарный поиск также называют дихотомия. Это простой и эффективный алгоритм поиска для элементов, у которых существует понятие порядка. Поиск работает на упорядоченном массиве. Поэтому для него необходимо либо сначала упорядочить данные, либо использовать его на структуре, которая сама обеспечивает упорядоченность (например бинарное дерево или куча).
Искомое значение сравнивается с элементом посередине. Если он больше, мы знаем что данные упорядочены по возрастанию, а значит все значения справа от него тоже больше. Таким образом мы отбрасываем половину массива правее этого элемента, и продолжаем с остатками.
Кроме точного поиска, этот алгоритм позволяет найти ближайший к искомому. Им будет последний оставшийся элемент.
Бинарный поиск разбивает интервалы на 2 половины, пока не дойдет до двух полуинтервалов, где у каждого размер 1. В конечном счете n элементов разделены на два элемента, в двух под-интервалах, двух интервалов, и т.д. То есть всё n бьется на произведение двоек. Значит количество таких операций разделения – это то, сколько двоек нужно перемножить, чтобы получить n. А это по определению двоичный логарифм, значит сложность алгоритма по времени –
O(log2(n)).