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

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

Мы начинаем с массива и элемента, который нам нужно найти.

Смотрим на середину массива. Мы берем количество элементов и делим его на 2. Представьте, что у нас есть часть массива слева, а другая часть справа.

Если предмет, который у нас есть, ниже, чем тот, который мы ищем, то он должен быть в правой части, чтобы мы могли полностью отбросить часть справа.

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

В конце концов, вы получите товар (или вернетеnullесли товар не найден).

В конце концов, если в массиве было 8 элементов, мы находим элемент не более чем за 4 шага.

Если бы в массиве было 32 элемента, в худшем случае у нас будет максимум 6 шагов. По сравнению с 32 в линейном поиске, это огромная оптимизация!

Бинарный поиск имеетO(log n) сложность.

Вот его возможная реализация:

const binarySearch = (list, item) => {
  let low = 0
  let high = list.length - 1

while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid]

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">===</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">mid</span>
}

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">&gt;</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#a6e22e">high</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
} <span style="color:#66d9ef">else</span> {
  <span style="color:#a6e22e">low</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
}

}

return null //if not found }

Как это работает? Мы получаемlistмассив и значение элемента, которое мы ищем. Затем мы инициализируемlowзначение 0 изначально, аhighзначение до последнего индекса в списке. Сначала мы смотрим на средний элемент, и если это то, что мы ищем, мы возвращаем его, и все готово. Если нет, мы устанавливаемlowили жеhighvalues, чтобы смотреть только на левую или правую часть массива, и мы повторяем процесс, пока не найдем элемент.

Возвращаем индекс элемента в массиве:

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

Мы возвращаемnullесли элемент не найден:

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

Скачать мою бесплатнуюРуководство для начинающих по JavaScript


Больше руководств по js: