Реализация бинарного поиска в массиве

Условие

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

function binSearch(arr, target) {
  // code
}

/* test 1— */
/* test 2— */

// const arr = ...;
// const result = binSearch(arr, ?);
// console.log(result);

Ответ

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

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

Предполагается сортировка по возрастанию. Пустой массив сразу даёт -1. Обе границы включены, поэтому используется <=, а после сравнения середина исключается. Время O(log n), дополнительная память O(1).