Алгоритмы 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 соответственно.
Вот и все для двоичного поиска! Спасибо за прочтение.