Бинарный поиск в JavaScript 

Поиск - одна из наиболее часто выполняемых задач в области компьютерных наук. Для повышения эффективности поиска существует множество алгоритмов и структур данных.

В этой статье мы рассмотрим идею бинарного поиска и то, как реализовать ее в JavaScript.

Бинарный поиск - это очень простой, интуитивно понятный, но эффективный алгоритм поиска. Единственное предостережение: он работает только с отсортированными массивами, поэтому может потребоваться некоторая предварительная обработка наших данных для их сортировки.

Понимание бинарного поиска

Бинарный поиск - это алгоритм «разделяй и властвуй», который делит массив примерно пополам каждый раз, когда проверяет, является ли элемент массива тем, который мы ищем.

Другими словами, мы разделяем проблему на более простые задачи, пока она не станет достаточно простой, чтобы решать их напрямую. Предположим, у нас есть отсортированный массив (в порядке возрастания), и посмотрим на этапы бинарного поиска:

1. Найдите средний элемент данного массива.
2. Сравните средний элемент со значением, которое мы ищем (называемым ключом).Если ключ меньше среднего элемента, ищите в левой половине.Если ключ больше среднего элемента, ищите в правой половине.Если ключ равен среднему элементу, вернуть индекс среднего элемента.
3. Если ключ меньше среднего элемента, ищите в левой половине.
4. Если ключ больше среднего элемента, ищите в правой половине.
5. Если ключ равен среднему элементу, вернуть индекс среднего элемента.
6. Продолжайте шаги 1, 2, пока не останется один элемент.
7. Если ключ все еще не найден, верните -1.

Чтобы лучше понять это, давайте рассмотрим пример того, почему мы можем просто отбрасывать половину текущего диапазона поиска каждый раз, когда проверяем элемент:

Подобно этому первому разбиению, мы можем продолжать «нырять» в массив, пока не найдем элемент или не найдем только одного кандидата на ключ.

В этом случае у нас остался только один возможный кандидат на ключ, и оказалось, что он соответствует искомому элементу.

Как вы можете видеть в примере, нам потребовалось относительно немного сравнений, чтобы найти нужный нам элемент. А именно, нам нужно было всего четыре сравнения, чтобы найти элемент в массиве из 11 элементов. Мы более подробно рассмотрим эффективность бинарного поиска позже, но уже должно быть ясно, что он превосходит простые алгоритмы поиска, такие как линейный поиск.

Реализация бинарного поиска в JavaScript

Теперь, когда мы рассмотрели логику бинарного поиска, давайте реализуем ее в JavaScript:

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);

        if (sortedArray[middle] === key) {
            // found the key
            return middle;
        } else if (sortedArray[middle] < key) {
            // continue searching to the right
            start = middle + 1;
        } else {
            // search searching to the left
            end = middle - 1;
        }
    }
	// key wasn't found
    return -1;
}

Здесь мы используем две переменные start и end для отслеживания текущего подмассива, который мы ищем. Мы находим средний элемент, а затем проверяем, равен ли он, меньше или больше, чем key.

Как объяснялось ранее, учитывая, что у нас есть отсортированный массив, мы можем отбросить половину элементов в массиве. Мы достигаем этого в коде, изменяя переменную start или end, в зависимости от того, где мы продолжаем поиск. Если текущий элемент, на который мы смотрим, меньше ключа, мы меняем start на middle + 1 и эффективно отбрасываем текущий элемент и все элементы меньше этого.

Эффективность бинарного поиска

Временная сложность бинарного поиска составляет O (log 2 n), где n - количество элементов в массиве. Это намного лучше по сравнению с линейным поиском, который имеет временную сложность O (n). Как и многие другие алгоритмы поиска, бинарный поиск - это алгоритм на месте. Это означает, что он работает непосредственно с исходным массивом без создания копий.

Однако мы должны помнить, что бинарный поиск работает только с отсортированными массивами. Сам этап сортировки, если используется эффективный алгоритм сортировки, имеет сложность O (nlogn). Это означает, что в большинстве случаев, если массив небольшой или если нам нужно выполнить поиск в нем только один раз, лучше использовать алгоритм грубой силы (например, линейный поиск).

Учитывая это, бинарный поиск действительно эффективен, когда нам нужно выполнять повторный поиск в больших массивах. Как упоминалось ранее, для массива из 11 элементов нам потребовалось всего 4 сравнения (сравнения - самые сложные задачи из всех поисковых алгоритмов). Однако, если бы у нас был массив из 10 000 000 элементов, нам нужно было бы проверить только 24 элемента, то есть 0,0002% от всего массива.

Вывод

В этой статье мы рассмотрели бинарный поиск. Его простая, интуитивно понятная и эффективная логика и реализация делают его очень популярным алгоритмом для демонстрации стратегии «разделяй и властвуй» .