Бинарный поиск — проект на JavaScript

JS.21 · Алгоритмы

Задача

Найти индекс значения в отсортированном массиве.

Алгоритм

Диапазон делится пополам: если середина меньше искомого — ищем правее, иначе левее.

Исходный код

// Бинарный поиск
function binarySearch(a, x) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const m = (lo + hi) >> 1;
    if (a[m] === x) return m;
    a[m] < x ? (lo = m + 1) : (hi = m - 1);
  }
  return -1;
}

console.log('индекс 7:', binarySearch([1, 3, 5, 7, 9, 11, 13], 7));
console.log('индекс 8:', binarySearch([1, 3, 5, 7, 9, 11, 13], 8));

Пояснения

Оператор >>1 делит на два с отбрасыванием дробной части. Сложность O(log n).