Как работает алгоритм бинарного поиска?

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

Принцип работы

Алгоритм начинает с определения границ массива: левой (low) и правой (high). Затем он находит средний элемент (mid) и сравнивает его с искомым значением (target). Возможны три случая:

• Если target равен mid, элемент найден.
• Если target меньше mid, поиск продолжается в левой половине (high = mid - 1).
• Если target больше mid, поиск продолжается в правой половине (low = mid + 1).

Процесс повторяется, пока low не станет больше high, что означает отсутствие элемента.

Пример кода на JavaScript

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      return mid; // элемент найден
    } else if (arr[mid] < target) {
      low = mid + 1; // ищем в правой половине
    } else {
      high = mid - 1; // ищем в левой половине
    }
  }
  return -1; // элемент не найден
}

Применение

Бинарный поиск широко используется в базах данных, поисковых системах, а также в стандартных библиотеках языков программирования (например, Array.binarySearch в Java). Он применим только к отсортированным данным, поэтому перед использованием массив должен быть отсортирован.

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