Алгоритм бинарного поиска: пошаговое объяснение

Почему этот алгоритм важен?

Алгоритм бинарного поиска — это эффективный метод поиска, который позволяет:

• 🧠 Быстро находить элементы в отсортированных массивах с логарифмической сложностью O(log n)
• ⚡ Существенно ускорять поиск по сравнению с линейным перебором (O(n))
• 🎯 Решать широкий класс оптимизационных задач с использованием "бинарного поиска по ответу"
• 🔍 Понять фундаментальный подход "разделяй и властвуй"
• 🌟 Развить интуицию для работы со сложностью O(log n)

Постановка задачи

Классическая формулировка:

Дан отсортированный массив элементов и целевой элемент. Необходимо определить, присутствует ли целевой элемент в массиве, и если да, то вернуть его индекс. Если элемент отсутствует, вернуть -1 (или другое указание на отсутствие).

Входные данные:

• Отсортированный массив элементов arr
• Целевой элемент target

Выходные данные:

• Индекс целевого элемента в массиве или -1, если элемент отсутствует

Примеры:

// Первый пример ✅
Input: arr = [1, 3, 5, 7, 9, 11], target = 5
Output: 2
Объяснение: Элемент 5 находится в массиве на позиции с индексом 2

// Второй пример ✅
Input: arr = [1, 2, 3, 4, 5, 6], target = 0
Output: -1
Объяснение: Элемент 0 отсутствует в массиве

// Третий пример ✅
Input: arr = [-10, -5, 0, 3, 7], target = 3
Output: 3
Объяснение: Элемент 3 находится в массиве на позиции с индексом 3

Принцип работы алгоритма

Бинарный поиск работает по принципу "разделяй и властвуй", постоянно уменьшая область поиска вдвое:

1. Инициализация: Устанавливаем указатели left и right на границы массива
2. Поиск: Пока left ≤ right:
   • Вычисляем средний индекс mid = (left + right) / 2
   • Если arr[mid] == target, возвращаем mid (элемент найден)
   • Если arr[mid] < target, обновляем left = mid + 1 (ищем в правой части)
   • Если arr[mid] > target, обновляем right = mid - 1 (ищем в левой части)
3. Завершение: Если цикл завершился, элемент не найден, возвращаем -1

Пошаговое объяснение с примером

Рассмотрим массив [1, 3, 5, 7, 9, 11] и целевой элемент 5.

Шаг 1: Инициализация

Устанавливаем:

• left = 0 (начало массива)
• right = 5 (конец массива)

Шаг 2: Первая итерация

• Вычисляем mid = (0 + 5) / 2 = 2 (округляем вниз)
• Проверяем: arr[mid] = arr[2] = 5
• 5 == 5 — элемент найден!
• Возвращаем mid = 2

Если бы мы искали 7, процесс продолжился бы:

Шаг 3: Вторая итерация (для target = 7)

• Так как arr[mid] = 5 < 7, обновляем left = mid + 1 = 3
• Новые указатели: left = 3, right = 5
• Вычисляем mid = (3 + 5) / 2 = 4
• Проверяем: arr[mid] = arr[4] = 9
• 9 > 7, обновляем right = mid - 1 = 3

Шаг 4: Третья итерация (для target = 7)

• Новые указатели: left = 3, right = 3
• Вычисляем mid = (3 + 3) / 2 = 3
• Проверяем: arr[mid] = arr[3] = 7
• 7 == 7 — элемент найден!
• Возвращаем mid = 3

Подходы к реализации

Решение 1: Итеративный подход 🔍

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

// Пример использования
const arr = [1, 3, 5, 7, 9, 11];
const target = 5;
console.log(binarySearch(arr, target)); // 2

Анализ решения:

✅ Простая итеративная реализация без рекурсии

✅ Оптимальная временная сложность O(log n)

✅ Константная пространственная сложность O(1)

✅ Защита от переполнения при вычислении среднего индекса

Решение 2: Рекурсивный подход 🚀

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // Базовый случай: область поиска пуста
  if (left > right) {
    return -1;
  }
  
  // Вычисляем средний индекс
  const mid = left + Math.floor((right - left) / 2);
  
  // Нашли элемент
  if (arr[mid] === target) {
    return mid;
  }
  
  // Рекурсивно ищем в левой или правой части
  if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

// Пример использования
const arr = [1, 3, 5, 7, 9, 11];
const target = 5;
console.log(binarySearchRecursive(arr, target)); // 2

Характеристики:

✅ Элегантная рекурсивная реализация

✅ Временная сложность O(log n)

❌ Пространственная сложность O(log n) из-за стека вызовов

❌ Возможно переполнение стека для очень больших массивов

Решение 3: Поиск первого вхождения элемента 🔧

function binarySearchFirstOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 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 arr = [1, 3, 5, 5, 5, 7, 9, 11];
const target = 5;
console.log(binarySearchFirstOccurrence(arr, target)); // 2 (первое вхождение)

Преимущества и недостатки:

✅ Находит первое вхождение элемента в массиве с дубликатами

✅ Временная сложность остается O(log n)

✅ Константная пространственная сложность O(1)

❌ Немного сложнее базовой реализации

Решение 4: Поиск последнего вхождения элемента 📊

function binarySearchLastOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    
    // Нашли элемент, но продолжаем поиск вправо
    // для нахождения последнего вхождения
    if (arr[mid] === target) {
      result = mid;
      left = mid + 1;
    }
    // Ищем в правой части
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // Ищем в левой части
    else {
      right = mid - 1;
    }
  }
  
  return result;
}

// Пример использования
const arr = [1, 3, 5, 5, 5, 7, 9, 11];
const target = 5;
console.log(binarySearchLastOccurrence(arr, target)); // 4 (последнее вхождение)

Особенности:

✅ Находит последнее вхождение элемента в массиве с дубликатами

✅ Временная сложность O(log n)

✅ Константная пространственная сложность O(1)

❌ Требует дополнительной логики по сравнению с базовой реализацией

Расширенные варианты бинарного поиска

1. Поиск в циклически сдвинутом массиве

function searchInRotatedArray(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    
    if (arr[mid] === target) {
      return mid;
    }
    
    // Определяем, в какой части массива находимся
    if (arr[left] <= arr[mid]) {
      // Левая часть отсортирована
      if (arr[left] <= target && target < arr[mid]) {
        // Цель в отсортированной левой части
        right = mid - 1;
      } else {
        // Цель в правой части
        left = mid + 1;
      }
    } else {
      // Правая часть отсортирована
      if (arr[mid] < target && target <= arr[right]) {
        // Цель в отсортированной правой части
        left = mid + 1;
      } else {
        // Цель в левой части
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

// Пример использования
const rotatedArr = [4, 5, 6, 7, 0, 1, 2];
const target = 0;
console.log(searchInRotatedArray(rotatedArr, target)); // 4

2. Бинарный поиск по ответу

// Пример: Найти минимальное пороговое значение, такое что функция условия возвращает true
function binarySearchAnswer(low, high, condition) {
  let result = -1;
  
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    
    if (condition(mid)) {
      result = mid;
      high = mid - 1; // Ищем минимальное значение
    } else {
      low = mid + 1;
    }
  }
  
  return result;
}

// Пример использования: 
// Найти первое число X, такое что X^2 >= K
function findFirstNumberWhoseSquareGreaterOrEqual(K) {
  return binarySearchAnswer(0, K, (x) => x * x >= K);
}

console.log(findFirstNumberWhoseSquareGreaterOrEqual(17)); // 5 (так как 5^2 = 25 >= 17)

3. Поиск ближайшего элемента

function findClosestElement(arr, target) {
  if (arr.length === 0) return -1;
  
  // Если target меньше первого элемента
  if (target <= arr[0]) return 0;
  
  // Если target больше последнего элемента
  if (target >= arr[arr.length - 1]) return arr.length - 1;
  
  let left = 0;
  let 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;
    }
  }
  
  // После завершения цикла, left > right
  // Нужно сравнить два соседних элемента и выбрать ближайший
  if (Math.abs(arr[left] - target) < Math.abs(arr[right] - target)) {
    return left;
  } else {
    return right;
  }
}

// Пример использования
const arr = [1, 3, 6, 9, 12];
const target = 7;
console.log(findClosestElement(arr, target)); // 2 (element 6 is closest to 7)

Анализ временной и пространственной сложности

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

• Наилучший случай: O(1) — если искомый элемент находится в середине массива
• Средний случай: O(log n)
• Наихудший случай: O(log n)

Пространственная сложность:

• Итеративная реализация: O(1)
• Рекурсивная реализация: O(log n) из-за стека вызовов

Сравнение с линейным поиском:

Визуализация работы алгоритма

Рассмотрим процесс поиска элемента 7 в массиве [1, 3, 5, 7, 9, 11]:

Итерация 1:
Массив: [1, 3, 5, 7, 9, 11]
         L     M     R
left = 0, right = 5, mid = 2
arr[mid] = 5 < 7, поэтому left = mid + 1 = 3

Итерация 2:
Массив: [1, 3, 5, 7, 9, 11]
               L  M  R
left = 3, right = 5, mid = 4
arr[mid] = 9 > 7, поэтому right = mid - 1 = 3

Итерация 3:
Массив: [1, 3, 5, 7, 9, 11]
               LMR
left = 3, right = 3, mid = 3
arr[mid] = 7 == 7, элемент найден!

Результат: 3 (индекс элемента 7)

Распространенные ошибки и нюансы

1. Ошибка переполнения при вычислении среднего индекса

Классическая формула mid = (left + right) / 2 может привести к переполнению целочисленного типа, если left и right достаточно большие. Безопасная формула:

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

2. Неправильные граничные условия цикла

Распространенные варианты:

• while (left <= right) — стандартное условие, позволяющее обрабатывать и случай одного элемента
• while (left < right) — требует дополнительной проверки после цикла

3. Ошибки с обновлением указателей

Важно правильно обновлять указатели:

• Для правой части: left = mid + 1
• Для левой части: right = mid - 1

Ошибка с присвоением right = mid или left = mid может привести к бесконечному циклу.

4. Равенство элементов и дубликаты

Классический бинарный поиск не гарантирует нахождение первого или последнего вхождения элемента при наличии дубликатов. Для этих случаев требуются специальные реализации.

Практические применения

1. Поиск в отсортированных коллекциях данных

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

2. Алгоритмы оптимизации

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

3. Компиляторы и интерпретаторы

Используется для поиска в таблицах символов и константных пулах.

4. Системные библиотеки и API

Многие стандартные библиотеки предоставляют реализации бинарного поиска (например, Arrays.binarySearch() в Java, std::lower_bound() в C++).

5. Компьютерные игры

Алгоритмы искусственного интеллекта и поиска пути часто используют бинарный поиск как составную часть.

Оптимизации и вариации

1. Интерполяционный поиск

Улучшение бинарного поиска для равномерно распределенных данных:

function interpolationSearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right && target >= arr[left] && target <= arr[right]) {
    // Формула для лучшего приближения позиции
    const pos = left + Math.floor(
      ((target - arr[left]) * (right - left)) / 
      (arr[right] - arr[left])
    );
    
    if (arr[pos] === target) {
      return pos;
    }
    
    if (arr[pos] < target) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }
  
  return -1;
}

2. Экспоненциальный поиск

Полезен, когда размер массива неизвестен или для поиска в неограниченных последовательностях:

function exponentialSearch(arr, target) {
  if (arr[0] === target) {
    return 0;
  }
  
  // Находим диапазон для бинарного поиска
  let i = 1;
  while (i < arr.length && arr[i] <= target) {
    i *= 2;
  }
  
  // Выполняем бинарный поиск в найденном диапазоне
  return binarySearch(
    arr, 
    target, 
    i / 2, 
    Math.min(i, arr.length - 1)
  );
}

3. Галопирующий (скачущий) поиск

Улучшение для поиска в связных списках или при дорогостоящем доступе к элементам:

function jumpSearch(arr, target) {
  const n = arr.length;
  const step = Math.floor(Math.sqrt(n));
  
  // Находим блок, где может быть элемент
  let prev = 0;
  while (arr[Math.min(step, n) - 1] < target) {
    prev = step;
    step += Math.floor(Math.sqrt(n));
    if (prev >= n) {
      return -1;
    }
  }
  
  // Линейный поиск в найденном блоке
  while (arr[prev] < target) {
    prev++;
    if (prev === Math.min(step, n)) {
      return -1;
    }
  }
  
  // Проверяем найденный элемент
  if (arr[prev] === target) {
    return prev;
  }
  
  return -1;
}

Заключение

Бинарный поиск — это мощный и элегантный алгоритм, который:

• 🌟 Обеспечивает логарифмическую сложность поиска O(log n), что делает его чрезвычайно эффективным для больших массивов
• 🧩 Служит основой для многих других алгоритмов и методов оптимизации
• 🛠️ Имеет множество вариаций и расширений для решения различных задач
• 📚 Является фундаментальным алгоритмическим шаблоном, который должен знать каждый разработчик

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

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