Концепция бинарного поиска

Что такое бинарный поиск?

Представьте, что вы загадали число от 1 до 100, а я пытаюсь его угадать. Вместо перебора (1, 2, 3...), я назову 50. Вы скажете "больше". Я отброшу всю левую половину и назову 75. Это и есть бинарный поиск (поиск делением пополам).

Главное условие: бинарный поиск работает исключительно на отсортированном массиве данных! Каждым шагом он уменьшает область поиска ровно в 2 раза, что делает его невероятно быстрым: сложность составляет всего O(log N).