алгоритмы, двоичный поиск

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

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

Смотрим на середину массива. Берём количество элементов и делим его на 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]

    if (guess === item) {
      return mid
    }

    if (guess > item) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  return null //if not found
}

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

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

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