Что такое бинарный поиск?

Бинарный поиск — эффективный алгоритм поиска в отсортированном массиве

Бинарный поиск (Binary Search) — это алгоритм поиска элемента в отсортированном массиве, который работает по принципу "разделяй и властвуй". Вместо того чтобы проверять каждый элемент по очереди (линейный поиск), алгоритм делит массив пополам и определяет, в какой половине находится искомый элемент.

Как это работает

Представь, что ты ищешь слово в словаре:

1. Ты открываешь словарь посередине
2. Смотришь на слово: оно раньше или позже нужного?
3. Если раньше — ты открываешь правую половину и повторяешь
4. Если позже — открываешь левую половину
5. Процесс повторяется, пока не найдёшь слово

Временная сложность

• Линейный поиск: O(n) — в худшем случае нужно проверить все элементы
• Бинарный поиск: O(log n) — намного быстрее для больших массивов

Для массива из 1 млн элементов:

• Линейный поиск: максимум 1 млн операций
• Бинарный поиск: максимум ~20 операций

Реализация на TypeScript

// Рекурсивная реализация
function binarySearch(
  arr: number[],
  target: number,
  left: number = 0,
  right: number = arr.length - 1
): number {
  if (left > right) {
    return -1; // Элемент не найден
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid; // Элемент найден
  } else if (arr[mid] < target) {
    // Ищем в правой половине
    return binarySearch(arr, target, mid + 1, right);
  } else {
    // Ищем в левой половине
    return binarySearch(arr, target, left, mid - 1);
  }
}

// Использование
const numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(numbers, 7)); // 3
console.log(binarySearch(numbers, 8)); // -1

Итеративная реализация (эффективнее)

function binarySearchIterative(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1; // Ищем справа
    } else {
      right = mid - 1; // Ищем слева
    }
  }

  return -1; // Не найдено
}

Типичные ошибки

// ❌ Неправильно: целочисленное переполнение
const mid = (left + right) / 2; // Может переполниться

// ✅ Правильно
const mid = Math.floor((left + right) / 2);
// или
const mid = left + Math.floor((right - left) / 2);

Практическое применение на фронтенде

// Автодополнение (поиск первого совпадения)
function findFirstMatch(arr: string[], prefix: string): number {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid].startsWith(prefix)) {
      result = mid;
      right = mid - 1; // Ищем более раннее совпадение
    } else if (arr[mid] < prefix) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

// Поиск диапазона (от и до какого индекса находятся элементы)
function searchRange(arr: number[], target: number): [number, number] {
  const findFirst = (arr: number[], target: number): number => {
    let left = 0, right = arr.length - 1, result = -1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (arr[mid] === target) {
        result = mid;
        right = mid - 1;
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return result;
  };

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

  return [findFirst(arr, target), findLast(arr, target)];
}

const arr = [5, 7, 7, 8, 8, 10];
console.log(searchRange(arr, 8)); // [3, 4]

Ограничения

• Массив должен быть отсортирован — это главное условие
• Неэффективен для несортированных данных
• Для динамических данных нужно поддерживать сортировку