Алгоритмы Javascript - двоичный поиск

В этом посте мы собираемся обсудить алгоритм поиска, известный как бинарный поиск. Бинарный поиск, как и сортировка слиянием, основан на принципе разделяй и властвуй. Это очень простая концепция, но при реализации может оказаться непростой задачей. Двоичный поиск выполняется за логарифмическое время O (log n), что делает его значительно более оптимальным подходом, чем последовательный поиск, который выполняется за линейное время O (n). Однако есть одна загвоздка: двоичный поиск работает, только если входной массив уже отсортирован.

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

let binarySearchIterative = (arr, key) => {
    let min = 0,
        max = arr.length - 1,
        guess;
    while (min <= max) {
        guess = Math.floor(min + ((max - min) / 2));
        if (arr[guess] === key) {
            return key + " found at position " + guess;
        } else if (arr[guess] < key) {
            min = guess + 1;
        } else {
            max = guess - 1;
        }
    }
    return -1;
};

Функция принимает в качестве входных данных массив и ключ (значение, которое вы ищете). Он устанавливает для переменной «min» значение 0 (для первого индекса массива), а для переменной «max» значение длины массива минус 1 (последний индекс массива). Затем, хотя значение min меньше, чем значение max, он устанавливает переменную «guess» равной медиане массива и начинает сравнения. В этом случае я использую формулу min + (max - min) / 2, чтобы избежать переполнения на более длинных массивах, но это не всегда необходимо. Вы можете просто использовать (max + min) / 2, если знаете, что длина массива не очень длинная. Если значение массива в предположении позиции совпадает с ключом, значит, оно найдено и возвращается. Если значение массива в позиции guess меньше ключа, тогда значение min обновляется до значения переменной guess плюс 1, что означает, что следующий поиск должен быть только в правой половине массива. В противном случае максимальное значение обновляется до значения «предположение минус 1», что означает, что следующий поиск должен выполняться только в левой половине массива. После min ›max подтверждается, что ключа нет в массиве, и возвращается -1.

Теперь давайте посмотрим на рекурсивную версию:

let binarySearchRecursive = (arr, key, min, max) => {
    if (min > max) {
        return -1;
    } else {
        let guess = Math.floor(min + ((max - min) / 2));
        if (arr[guess] === key) {
            return key + " found at position " + guess;
        } else if (arr[guess] < key) {
            return binarySearchRecursive(arr, key, guess + 1, max);
        } else {
            return binarySearchRecursive(arr, key, min, guess - 1);
        }
    }
};

Идея здесь та же, только с использованием рекурсивного метода вместо итеративного. При запуске этой программы переменные min и max должны быть такими же, как и для итеративной версии - 0 и длина массива минус 1 соответственно.

Вот и все для двоичного поиска! Спасибо за прочтение.