Алгоритмы. Бинарный поиск. Бинарные деревья.

binarySearch.md

Работает только для отсортированных массивов.

function binarySearch(
  array,
  element,
  start = 0,
  end = array.length - 1,
) {
  if (end < start) return -1;
  
  const middle = Math.floor((start + end) / 2);

  return element === array[middle] ?
    middle :
      element < array[middle] ?
      binarySearch(array, element, start, middle - 1) :
      binarySearch(array, element, middle + 1, end);
}

console.log(binarySearch([3, 4, 5, 6, 7, 8, 9, 10], 5)); // 2
console.log(binarySearch([3, 4, 5, 6, 7, 8, 9, 10], 2)); // -1

Since in each recursive call we break down the search space in half, our problem size decreases exponentially, taking our worst case time complexity from O(n) to O(log n).