Представьте, что вы ищете конкретную книгу в библиотеке с миллионами книг. Хорошим алгоритмом для быстрого поиска нужной книги является бинарный поиск.
Бинарный поиск работает, разделяя библиотеку на две части и проверяя, находится ли искомая книга в левой или правой части. Затем вы продолжаете делить ту часть, где может быть книга, пока не найдете книгу или не определите, что ее там нет. Это похоже на то, как бинарный поиск работает с массивами, разделяя массив пополам и проверяя, находится ли целевое значение в левой или правой половине, пока цель не будет найдена или не будет определено, что ее нет в массиве.
Для поиска определенного элемента в большом массиве вы можете использовать алгоритм бинарного поиска. Это эффективный алгоритм поиска в отсортированном массиве путем многократного деления интервала поиска пополам. Вот пример реализации на JavaScript:
function binarySearch(arr, target) { let left = 0, right = arr.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }
- Функция binarySearch принимает массив
arr
и целевое значениеtarget
в качестве входных данных. let left = 0, right = arr.length - 1;
устанавливает две переменныеleft
иright
для хранения индексов самого левого и самого правого элементов в массиве. Самый правый индекс равен длине массива минус 1, потому что массивы в JavaScript индексируются 0.- Цикл while
while (left <= right)
будет выполняться до тех пор, пока индексleft
меньше или равен индексуright
. const mid = Math.floor((left + right) / 2);
вычисляет средний индекс, беря нижний предел среднего значенияleft
иright
.- Оператор if
if (arr[mid] === target)
проверяет, равно ли значение индексаmid
целевому. Если это так, функция возвращает индексmid
. - Оператор else if
else if (arr[mid] < target)
проверяет, меньше ли значение индексаmid
целевого. Если это так, значениеleft
обновляется доmid + 1
, чтобы поиск сосредоточился на правой половине массива. - Оператор else
else
выполняется, когда значение индексаmid
больше целевого. В этом случае значениеright
обновляется доmid - 1
, чтобы поиск сосредоточился на левой половине массива. - Функция возвращает -1, если цель не найдена в массиве, что делается вне цикла while.
Алгоритм бинарного поиска имеет несколько ограничений:
- Входной массив должен быть отсортирован: Алгоритм бинарного поиска работает только с отсортированными массивами. Если массив не отсортирован, алгоритм не даст правильных результатов.
- Структура данных должна быть доступна по индексу: Алгоритм бинарного поиска требует произвольного доступа к элементам массива. Если структура данных не разрешает доступ по индексу, алгоритм использовать нельзя.
- Временная сложность является логарифмической: хотя временная сложность алгоритма бинарного поиска является логарифмической, что очень быстро, для больших массивов она все же может быть медленной.
- Его нельзя использовать с повторяющимися значениями: если массив содержит повторяющиеся значения, алгоритм бинарного поиска может работать некорректно. Алгоритм предполагает, что значения в массиве уникальны, а дубликаты могут привести к неверным результатам.
- Он может не подходить для данных, которые часто меняются: если данные в массиве часто меняются, алгоритм бинарного поиска может быть не лучшим выбором, поскольку массив необходимо сортировать после каждого изменения.