Двоичный поиск – это алгоритм поиска, используемый в отсортированных массивах, который предполагает непрерывное деление массива пополам. Алгоритм значительно быстрее обычного линейного поиска, сокращая временную сложность с O(n) до O(log n).
Что все это значит?
Допустим, у вас есть отсортированный массив чисел, что-то вроде [1, 3, 4, 6, 7, 8, 9], и вы хотите проверить, есть ли в массиве число 7. Как бы вы это реализовали?
Ну, самый простой способ сделать это — просто пройти один раз по массиву и для каждого элемента проверить, равен ли он 7. Если мы дошли до конца массива и ни один элемент не равен, то мы я знаю, что 7 не существует в массиве. Этот метод называется Линейный поиск.
Линейный поиск невероятно интуитивно понятен, но он может быть довольно неэффективным для поиска в большом наборе данных. Если бы наш массив состоял не из семи чисел, а из миллионов или миллиардов элементов (довольно распространенное явление в эпоху огромных баз данных) и нам приходилось бы выполнять тысячи поисков, линейный поиск был бы изнурительно медленным.
Итак, как мы это исправим?
Мы можем воспользоваться важным свойством массива: то, что он отсортирован. Отсортированные массивы особенные, потому что независимо от того, где вы находитесь в отсортированном массиве, все числа, которые меньше, всегда будут с одной стороны, а все числа, которые больше, всегда будут с одной стороны.
Если мы просто начнем с вопроса, больше или меньше искомое число, чем число в середине нашего отсортированного массива (если оно равно тому, которое мы уже нашли с первой попытки!), мы можем немедленно отбросить половина массива, где число не может быть.
Затем мы можем повторить этот процесс, постоянно уменьшая вдвое длину подмассива и все ближе и ближе приближаясь к искомому числу.
Мы останавливаем поиск, когда «среднее число» равно искомому числу (число находится в массиве) или когда мы выбросили весь наш массив (число не находится в массиве).
Теперь, поскольку мы можем отбрасывать половину массива на каждой итерации, это займет не более log₂ длины отсортированного массива количества итераций, что означает поиск элемента в массиве из миллиарда чисел займет не более 30 операций (по сравнению с миллиардом при использовании линейного поиска). В этом вся прелесть бинарного поиска.
