Поиск: линейный и бинарный

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

🚶 Линейный поиск: просто и универсально

Линейный поиск — самый интуитивный алгоритм. Мы просто проверяем каждый элемент по очереди, пока не найдём нужный. Никаких умных трюков — только честный перебор.

Аналогия: вы ищете ключи в квартире. Проверяете прихожую, кухню, гостиную, спальню... по одной комнате, пока не найдёте. Нет системы — просто перебор.

// Линейный поиск: проверяем каждый элемент
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // нашли — возвращаем индекс
    }
  }
  return -1; // не нашли — возвращаем -1
}

const arr = [5, 3, 8, 1, 4, 7, 2, 9];

console.log(linearSearch(arr, 7)); // 5 (индекс 5)
console.log(linearSearch(arr, 6)); // -1 (нет такого элемента)

// Можно искать не только числа:
const names = ["Иван", "Мария", "Алексей", "Анна"];
console.log(linearSearch(names, "Алексей")); // 2
console.log(linearSearch(names, "Борис"));   // -1

Линейный поиск работает для любых данных — отсортированных и не отсортированных, чисел и строк и объектов. Это его главное преимущество. Когда данных мало или они не отсортированы — это правильный выбор.

🎯 Бинарный поиск: делим задачу пополам

Бинарный поиск — один из самых элегантных алгоритмов. Но есть важное условие: массив должен быть отсортирован. Без этого алгоритм не работает.

Аналогия: угадайте число от 1 до 1024. Вы спрашиваете: «Больше 512?» — «Нет». Теперь ищем в диапазоне 1–512. «Больше 256?» — «Да». Ищем в 257–512. Каждый вопрос отсекает половину вариантов. За 10 вопросов — точный ответ!

Каждый шаг вдвое сокращает область поиска. Это и есть O(log n) — количество раз, которое мы можем поделить n на 2 до получения 1.

📊 Пошаговая визуализация: ищем 7 в [1, 3, 5, 7, 9, 11, 13]

Повезло — нашли за один шаг! Теперь рассмотрим более сложный пример: ищем 5 в [1, 3, 5, 7, 9, 11, 13]:

Всего 3 шага для поиска в 7 элементах. Теперь подумайте: для миллиона элементов — максимум 20 шагов!

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

Итеративная реализация (через цикл while) — самая практичная:

function binarySearch(sortedArr, target) {
  let left = 0;                        // левая граница поиска
  let right = sortedArr.length - 1;   // правая граница поиска

  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // середина

    if (sortedArr[mid] === target) {
      return mid; // нашли! возвращаем индекс
    }

    if (sortedArr[mid] < target) {
      left = mid + 1; // target правее, сдвигаем левую границу
    } else {
      right = mid - 1; // target левее, сдвигаем правую границу
    }
  }

  return -1; // не нашли
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

console.log(binarySearch(arr, 7));   // 3
console.log(binarySearch(arr, 19));  // 9
console.log(binarySearch(arr, 6));   // -1 (нет такого)

// ВАЖНО: массив должен быть отсортирован!
// Бинарный поиск на неотсортированном массиве — неверный результат
const wrong = [5, 3, 8, 1, 4];
console.log(binarySearch(wrong, 3)); // НЕНАДЁЖНО! Результат непредсказуем

Разберём код:

• left и right — границы текущей области поиска
• mid = Math.floor((left + right) / 2) — индекс середины текущего диапазона
• Если нашли — возвращаем индекс
• Если arr[mid] < target — элемент правее, сдвигаем левую границу
• Если arr[mid] > target — элемент левее, сдвигаем правую границу
• Цикл завершается когда left > right — диапазон пуст, элемента нет

📊 Сравнение: O(n) vs O(log n)

Цифры красноречивее слов. Вот максимальное количество шагов при поиске элемента:

Миллиард элементов — бинарный поиск справится за 30 шагов. Линейный поиск потребует миллиард. Это не просто «быстрее» — это другой мир.

🎯 Когда какой поиск использовать

🛠️ Бинарный поиск в реальном JavaScript

В JavaScript нет встроенного бинарного поиска (в отличие от Python с bisect или Java с Collections.binarySearch). Но есть несколько способов использовать похожие идеи:

// indexOf — линейный поиск встроенный
const arr = [3, 7, 1, 9, 2];
console.log(arr.indexOf(9));   // 3 — линейный O(n)

// includes — тоже линейный
console.log(arr.includes(7));  // true — линейный O(n)

// find — линейный поиск с условием
const users = [
  { id: 1, name: "Иван" },
  { id: 2, name: "Мария" },
  { id: 3, name: "Алексей" }
];
const user = users.find(u => u.id === 2); // линейный O(n)
console.log(user); // { id: 2, name: "Мария" }

// Для бинарного поиска — используйте свою реализацию
// или библиотеку lodash (_.sortedIndexOf)
const sorted = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sorted, 9)); // 4 — O(log n)

Все встроенные методы поиска в JavaScript (indexOf, includes, find, findIndex) используют линейный поиск O(n). Для бинарного — пишите свою функцию или используйте специализированную библиотеку.

✅ Итоги урока и раздела

• Линейный поиск — O(n), работает на любых данных, простой код
• Бинарный поиск — O(log n), только для отсортированных данных, в разы быстрее
• Миллион элементов: линейный — 1 000 000 шагов, бинарный — 20 шагов
• Все встроенные JS-методы (indexOf, find) — линейный поиск
• Если поисков много в больших данных — сначала сортируем, потом бинарный поиск
• Бинарный поиск: ключевая проверка arr[mid] < target → сдвигаем left, иначе → сдвигаем right