Вступление

Поиск - одна из наиболее часто выполняемых задач в области компьютерных наук. Для повышения эффективности поиска существует множество алгоритмов и структур данных.

В этой статье мы рассмотрим идею двоичного поиска и то, как реализовать ее в JavaScript.

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

Понимание двоичного поиска

Двоичный поиск - это алгоритм «разделяй и властвуй» , который делит массив примерно пополам каждый раз, когда проверяет, является ли элемент массива тем, который мы ищем.

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

1. Найдите средний элемент данного массива.
2. Сравните средний элемент со значением, которое мы ищем (называемым ключом ).
   • Если ключ меньше среднего элемента, ищите в левой половине.
   • Если ключ больше среднего элемента, ищите в правой половине.
   • Если ключ равен среднему элементу, вернуть индекс среднего элемента.
3. Продолжайте шаги 1, 2, пока не останется единственный элемент.
4. Если ключ все еще не найден, верните -1.

Чтобы лучше понять это, давайте рассмотрим пример того, почему мы можем просто отбрасывать половину текущего диапазона поиска каждый раз, когда проверяем элемент:

{.ezlazyload}

Подобно этому первому разбиению, мы можем продолжать «нырять» в массив, пока не найдем элемент или не получим только одного кандидата на ключ.

{.ezlazyload}

В этом случае у нас остался только один возможный кандидат на ключ, и он оказался соответствующим искомому элементу.

Как вы можете видеть в примере, нам потребовалось относительно немного сравнений, чтобы найти нужный нам элемент. А именно, нам нужно было провести всего четыре сравнения, чтобы найти элемент в массиве из 11 элементов. Мы более подробно рассмотрим эффективность двоичного поиска позже, но уже должно быть ясно, что он превосходит простые алгоритмы поиска, такие как линейный поиск .

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

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

 function binarySearch(sortedArray, key){ 
 let start = 0; 
 let end = sortedArray.length - 1; 
 
 while (start <= end) { 
 let middle = Math.floor((start + end) / 2); 
 
 if (sortedArray[middle] === key) { 
 // found the key 
 return middle; 
 } else if (sortedArray[middle] < key) { 
 // continue searching to the right 
 start = middle + 1; 
 } else { 
 // search searching to the left 
 end = middle - 1; 
 } 
 } 
 // key wasn't found 
 return -1; 
 } 

Здесь мы используем две переменные, чтобы отслеживать start и end текущего подмассива, который мы ищем. Мы находим средний элемент, а затем проверяем, равен ли он, меньше или больше key .

Как объяснялось ранее, учитывая, что у нас есть отсортированный массив, мы можем отбросить половину элементов в массиве. Мы достигаем этого в коде, изменяя start или end переменную, в зависимости от того, где мы продолжаем поиск. Если текущий элемент, на который мы смотрим, меньше ключа, мы меняем start на middle + 1 и эффективно отбрасываем текущий элемент и все элементы меньше этого.

Эффективность двоичного поиска

Временная сложность двоичного поиска составляет O (log ~2~ n) , где n - количество элементов в массиве. Это намного лучше по сравнению с линейным поиском, который имеет временную сложность O (n) . Как и многие другие алгоритмы поиска, двоичный поиск - это алгоритм на месте. Это означает, что он работает непосредственно с исходным массивом без создания копий.

Однако мы должны помнить, что двоичный поиск работает только с отсортированными массивами. Сам этап сортировки, если используется эффективный алгоритм сортировки, имеет сложность O (nlogn) . Это означает, что в большинстве случаев, если массив небольшой или если нам нужно выполнить поиск только один раз, лучше использовать алгоритм грубой силы (например, линейный поиск).

Учитывая это, двоичный поиск действительно эффективен, когда нам нужно выполнять повторный поиск в больших массивах. Как упоминалось ранее, для массива из 11 элементов нам потребовалось всего 4 сравнения (сравнения являются наиболее трудоемкими задачами всех поисковых алгоритмов). Однако, если бы у нас был массив из 10 000 000 элементов, нам нужно было бы проверить только 24 элемента, то есть 0,0002% от всего массива.

Заключение

В этой статье мы рассмотрели двоичный поиск. Его простая, интуитивно понятная и эффективная логика и реализация делают его очень популярным алгоритмом для демонстрации стратегии «разделяй и властвуй».