Бинарный поиск в JavaScript
В прошлой статье мы говорили с вами о линейном поиске, который подойдет для поиска в небольших по объему не сортированных коллекциях. Однако, на практике, часто приходиться работать с крупными структурами данных, для поиска в которых лучше подходит бинарный поиск.
Представим, что вы играете в игру, в которой необходимо отгадать некоторое число, например, от 1-го до 100. Вы выбираете произвольное число. Если выбранное вами число больше искомого или меньше него, то вы получает подсказку.
Какой будет ваша стратегия? Будете ли вы выбирать числа случайно? Начнете ли вы с 1, затем с 2 и так далее, пока не отыщете искомое число? Но, конечно, желательно, уменьшить время поиска насколько это возможно. Следовательно, числа можно начать угадывать с 50, т.е. с середины, тем самым сразу отбрасывая ненужную половину. Далее можно взять середину – 75 - из диапазона 50 – 100. Если искомое число меньше (о том, что число меньше вам известно из подсказки, само число не известно) , то это означает, что число находится в диапазоне от 50 до 75, в противном случае в диапазоне от 75 до 100. Таким образом, деля последовательность пополам на все более мелкие части, вы в итоге найдете искомое число. Примерно так и работает бинарный поиск.
Важно отметить, что в отличие от линейного поиска, бинарный поиск использует отсортированный список. Для поиска значения сначала необходимо сравнить со средним элементом списка. Если они равны, искомое значение найдено. Если искомое значение больше, чем средний элемент, выполняется поиск в верхней половине списка. В обратном случае, если искомое значение меньше среднего значения списка, поиск нужно проводить в нижней половине списка. Список многократно делится пополам до тех пор, пока нужное значение не будет найдено или не останется элементов для поиска.
Для поиска цифры 9 в списке:
1 2 3 4 5 6 7 8 9 10
сначала мы находим средний элемент. Этот элемент находится в позиции Math.floor ((first + last) / 2), где first - первый индекс (индексация массивов начинается с нуля), а last - последний индекс. Math.floor() – округляет значение до ближайшего меньшего целого числа. Средний элемент в этом списке равен 5. Наше искомое значение 9 больше 5, поэтому мы ищем интересующее нас значение в срезе списка:
6 7 8 9 10
Средний элемент этого среза равен 8. Девять больше, чем 8, поэтому продолжаем поиск в срезе коллекции:
9 10
Средний элемент равен 9, искомое значение найдено.
Реализация бинарного поиска в JavaScript
Теперь давайте реализуем алгоритм двоичного поиска в JavaScript!
Мы создадим функцию binarySearch, которая принимает значение, которое необходимо найти и массив, в котором этот поиск будет осуществляться. Функция вернет позицию значения в списке в случае успеха. Если значение не будет найдено, возвращается -1. Вот реализация:
function binarySearch(value, list) {
let first = 0; // начальный индекс в массиве
let last = list.length - 1; // конечный индекс
let position = -1;
let found = false;
let middle;
while (found === false && first <= last) {
middle = Math.floor((first + last) / 2);
if (list[middle] == value) {
found = true;
position = middle;
} else if (list[middle] > value){ // значение в нижней части списка
last = middle - 1;
} else { // значение в верхней части списка
first = middle + 1;
}
}
return position;
}
Заключение
В этой и предыдущей статье мы рассмотрели, как реализовать линейный поиск и алгоритм двоичного поиска. Алгоритм линейного поиска проще и не требует отсортированного массива. Тем не менее, он неэффективен для использования с большими массивами. В худшем случае алгоритм должен будет искать все элементы, делая n сравнений (где n - количество элементов).
С другой стороны, алгоритм двоичного поиска требует, чтобы вы сначала отсортировали массив, и его сложнее реализовать. Тем не менее, он более эффективен, даже если учитывать стоимость сортировки. Например, для массива из 10 элементов будет сделано не более 4 сравнений в случае бинарного поиска против 10 для линейного поиска – здесь различие не очень существенно. Однако для массива с 1 000 000 элементов наихудший случай в бинарном поиске - всего 20 сравнений. Это огромное улучшение по сравнению с линейным поиском!
Знание того, как и где использовать бинарный поиск - это практический навык, который может сделать ваш код более эффективным.
-
Создано 03.01.2019 12:19:27
-
Михаил Русаков
Комментарии (0):
Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.