JavaScript: функция бинарного поиска по массиву

Сказать, что бинарный поиск на больших объемах данных работает в разы быстрее чем линейный — это не сказать ничего.

Суть двоичного поиска (binary) состоит в том, что бы разделить сортированный массив данных на две части, тем самым поняв куда нам стоит переместится в левую или правую часть. Тем самым мы отсекаем половину данных. Это уже неплохой рывок по скорости, неправда-ли? Далее проделываем то же самое с нужной половиной и так до конца пока не найдем нужное значение.

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

Повторюсь, массив данных должен быть отсортирован.

Пример бинарного поиска

let data = [-1,0,3,23,56,62];

const binSearch = function( nums, target ) {
  let left = 0;
  let right = nums.length - 1;
  let mid;
  
  while ( left <= right ) {
    mid = Math.round( ( right - left ) / 2) + left;
    
    if ( target === nums[mid] ) {
      return mid;
    } else if ( target < nums[mid] ) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  return -1;
}

console.log( binSearch( data, 23 ) );