Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Algorithms
Code

Алгоритм двоичного поиска в JavaScript

by
Difficulty:IntermediateLength:MediumLanguages:

Russian (Pусский) translation by Vera (you can also view the original English article)

В этом посте я буду сравнивать алгоритмы линейного поиска и бинарного поиска. Вы увидите псевдокод для каждого алгоритма, а также примеры и пошаговое руководство по его реализации.

Вступление

Как программист, вы хотите найти лучшее решение проблемы, чтобы ваш код был не только правильным, но и эффективным. Выбор неоптимального алгоритма может означать более длительное время завершения, повышенную сложность кода или, что еще хуже, ошибочную программу. Возможно, вы использовали алгоритм поиска, чтобы найти элементы в коллекции данных. Язык JavaScript имеет несколько методов, таких как find, для поиска элементов в массиве. Однако эти методы используют линейный поиск. Алгоритм линейного поиска начинается в начале списка и сравнивает каждый элемент со значением поиска, пока он не будет найден. Это хорошо, когда у вас есть небольшое количество элементов. Но когда вы ищите большие списки, которые содержат тысячи или миллионы элементов, вам нужен лучший способ найти элементы. Это когда вы будете использовать бинарный поиск. В этом уроке я объясню, как работает бинарный поиск и как реализовать алгоритм в JavaScript. Сначала рассмотрим алгоритм линейного поиска.

Линейный поиск

Мы начнем с объяснения того, как реализовать линейный поиск в JavaScript. Мы создадим функцию с именем linearSearch, которая принимает значение, являющееся целым числом или строкой, и массив в качестве параметров. Функция будет искать значение в каждом элементе массива и возвращать позицию значения в массиве, если оно найдено. Если значение отсутствует в массиве, оно вернет -1. Например, вызов linearSearch (1, [3, 4, 2, 1, 5]) вернет 3, а вызов linearSearch (0, [3, 4, 2, 1, 5]) вернет -1.

Вот некоторый псевдокод для нашей функции:

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

Вот JavaScript-реализация алгоритма линейного поиска:

Важно отметить, что алгоритм линейного поиска не должен использовать отсортированный список. Также алгоритм может быть настроен для использования в различных сценариях, таких как поиск массива объектов по ключу. Если у вас есть массив данных о клиентах, который включает ключи для имени и фамилии, вы можете проверить, есть ли в массиве клиент с указанным именем. В этом случае вместо проверки того, равен ли list[index] нашему поисковому значению, вы должны проверить list[index] .first.

В приведенном выше примере я использовал функцию linearSearch для массива из 5 элементов. В худшем случае, когда искомое значение отсутствует в списке или находится в конце списка, функция должна будет выполнить 5 сравнений. Поскольку наш массив настолько мал, нет необходимости оптимизировать его, используя другой алгоритм. Однако до определенного момента использование алгоритма линейного поиска более неэффективно, и тогда лучше использовать алгоритм двоичного поиска.

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

Представьте, что вы угадываете чисел. Вас попросят угадать число от 1 до 100. Если ваш номер слишком высокий или слишком низкий, вы получите подсказку. Какой будет ваша стратегия? Вы бы выбрали числа случайно? Начнете ли вы с 1, затем с 2 и так далее, пока не угадаете? Даже если у вас было неограниченное количество догадок, вы хотите сделать правильное предположение за минимальное количество попыток. Поэтому вы можете начать угадывать с 50. Если число больше, вы можете угадать с 75 раза. Если оно меньше, то это означает, что число находится в диапазоне от 50 до 75, и вы выбрали бы число, которое находится в середине. Вы будете продолжать в том же духе, пока не достигнете правильного номера. Это похоже на то, как работает бинарный поиск.

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

Для поиска 9 в списке:

Сначала мы находим средний элемент. Это элемент в позиции Math.floor((first + last)/2), где first - первый индекс, а last - последний индекс. Мы выбираем округление так, чтобы в случае, если результат является дробью, он становится целым числом. Средний элемент в этом списке равен 5. Наше поисковое значение 9 больше 5, поэтому мы ищем список:

Средний элемент этой части равен 8. Девять больше, чем 8, поэтому мы ищем список:

Средний элемент равен 9, поэтому мы можем остановить наш поиск здесь.

Вот некоторый псевдокод, который выражает вышеупомянутый алгоритм для двоичного поиска:

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

Теперь давайте закодируем алгоритм двоичного поиска в JavaScript!

Мы создадим функцию binarySearch, которая принимает значение и массив в качестве параметров. Он вернет индекс, где значение встречается в списке, если найдено. Если значение не найдено, возвращается -1. Это наша реализация, написанная на JavaScript:

Заключение

В этом уроке мы увидели, как реализовать линейный поиск и алгоритм двоичного поиска. Алгоритм линейного поиска проще и не требует отсортированного массива. Тем не менее, это неэффективно для использования с большими массивами. В худшем случае алгоритм должен будет искать все элементы, сравнивая их по n (где n - количество элементов).

С другой стороны, алгоритм двоичного поиска требует, чтобы вы сначала отсортировали массив, и его сложнее реализовать. Тем не менее, это более эффективно, даже если учитывать стоимость сортировки. Например, массив с 10 элементами будет делать не более 4 сравнений для бинарного поиска против 10 для линейного поиска - не такое большое улучшение. Однако для массива с 1 000 000 элементов наихудший случай в бинарном поиске - всего 20 сравнений. Это огромное улучшение по сравнению с линейным поиском!

Знание того, как использовать бинарный поиск, - это не просто вопрос практики для интервью. Это практический навык, который может сделать ваш код более эффективным.

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.