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

Представьте, что вы ищете значение в отсортированном массиве из 100 000 цен товаров. Встроенный метод JavaScript indexOf() проверяет каждый элемент с начала — это потенциально 100 000 сравнений. Бинарный поиск выполняет это максимум за 17 операций. Эта разница объясняет, почему алгоритм бинарного поиска в JavaScript важен и почему его стоит реализовать самостоятельно — ведь в JavaScript нет встроенного метода бинарного поиска.

В этой статье рассматривается принцип работы бинарного поиска, способы реализации итеративной и рекурсивной версий, а также ситуации, когда его следует использовать вместо линейного поиска.

Что такое бинарный поиск и почему он требует отсортированный массив?

Бинарный поиск — это алгоритм «разделяй и властвуй». Он работает путём многократного деления области поиска пополам, пока не найдёт целевое значение или не исчерпает все возможности.

Вот в чём загвоздка: он работает только с отсортированными массивами. Алгоритм предполагает, что если целевое значение больше среднего элемента, оно должно находиться в правой половине. Это предположение полностью нарушается на неотсортированных данных — вы получите неверные результаты без какой-либо ошибки.

Шаги алгоритма:

1. Найти средний элемент текущего диапазона поиска
2. Если он равен целевому значению, вернуть его индекс
3. Если целевое значение меньше, искать в левой половине
4. Если целевое значение больше, искать в правой половине
5. Повторять до нахождения или исчерпания диапазона поиска

Реализация бинарного поиска в JavaScript: итеративный подход

Итеративная версия использует цикл while и два указателя. Это предпочтительный подход для большинства случаев — читаемый, эффективный и использующий O(1) памяти.

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // Return the index
    } else if (arr[mid] < target) {
      start = mid + 1 // Search right half
    } else {
      end = mid - 1 // Search left half
    }
  }

  return -1 // Target not found
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

Обратите внимание, что функция возвращает индекс целевого элемента, а не логическое значение. На практике это почти всегда полезнее.

Рекурсивный бинарный поиск в JavaScript

Рекурсивная версия передаёт обновлённые граничные индексы при каждом вызове. Она элегантна, но использует O(log n) памяти стека — по одному фрейму на каждый рекурсивный вызов.

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

Одна распространённая ошибка: забыть написать return перед рекурсивным вызовом. Без него функция возвращает undefined, даже если элемент существует.

Сортировка перед поиском

Если ваш массив ещё не отсортирован, сначала необходимо его отсортировать. Стандартный метод JavaScript Array.sort() выполняет лексикографическую сортировку, что нарушает числовые сравнения:

[10, 9, 100].sort()                   // [10, 100, 9] — неправильно
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — правильно

Всегда используйте числовой компаратор для числовых массивов перед выполнением бинарного поиска.

Бинарный поиск против линейного поиска: когда что использовать

Для массива из 10 000 элементов линейный поиск требует до 10 000 сравнений. Бинарный поиск — максимум 14. Если вы выполняете однократный поиск в небольшом неотсортированном массиве, indexOf() подойдёт. Если вы многократно ищете в больших отсортированных данных, бинарный поиск — правильный инструмент.

Заключение

Бинарный поиск легко реализовать в JavaScript, как только вы поймёте требование отсортированного массива. По умолчанию используйте итеративную версию — она чище и избегает накладных расходов стека вызовов. Используйте рекурсивную версию, когда структура вашего кода от этого выигрывает, но не забывайте всегда писать return перед рекурсивным вызовом. И всегда проверяйте, что ваш массив отсортирован с правильным числовым компаратором перед выполнением поиска.

Часто задаваемые вопросы

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.