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

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

Зачем использовать бинарный поиск?

Алгоритм бинарного поиска очень эффективен для больших коллекций отсортированных данных. Его временная сложность равна O(log n), что означает, что время, необходимое для поиска элемента в наборе из n элементов, пропорционально log n. Это намного быстрее, чем время, необходимое для линейного поиска, который имеет временную сложность O(n).

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

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

Двоичный поиск с использованием рекурсии

const binarySearchRecursive = (arr, target, start = 0, end = arr.length - 1) => {
  if (start > end) {
  // target not found
    return -1; 
  }
  
  const mid = Math.floor((start + end) / 2);
  
  if (arr[mid] === target) {
  // target found
    return mid; 
  }
  
  if (target < arr[mid]) {
  // search in the left half
    return binarySearchRecursive(arr, target, start, mid - 1);
  } else {
  // search in the right half
    return binarySearchRecursive(arr, target, mid + 1, end);
  }
}
  1. В качестве входных данных мы берем массив, целевое значение, а также начальный и конечный индексы интервала поиска.
  2. Если начальный индекс больше конечного, мы return -1 указываем, что целевое значение не найдено. В противном случае мы вычисляем средний индекс (start + end) / 2 и сравниваем значение этого индекса с целевым значением. Math.floor() округляет полученное значение в меньшую сторону, если оно десятичное. например 9.5 округляется до 9 в меньшую сторону
  3. Если они равны, мы возвращаем средний индекс. В противном случае отбрасываем одну из половин и продолжаем поиск в оставшейся половине по результату сравнения.
  4. Мы повторяем этот процесс до тех пор, пока не будет найдено целевое значение или интервал поиска не станет пустым.

Двоичный поиск с использованием итерации

const binarySearchIterative = (arr, target) => {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === target) {
    // target found
      return mid;
    }
    
    if (target < arr[mid]) {
    // search in the left half
      end = mid - 1;
    } else {
    // search in the right half
      start = mid + 1; 
    }
  }
  
  // target not found
  return -1;
}
  1. Мы начинаем со всего массива в качестве интервала поиска.
  2. Мы используем цикл while для продолжения поиска до тех пор, пока начальный индекс не станет больше конечного индекса, указывая на то, что целевое значение не найдено.
  3. На каждой итерации мы вычисляем средний индекс (start + end) / 2 интервала поиска и сравниваем значение этого индекса с целевым значением.
  4. Если они равны, мы возвращаем средний индекс. В противном случае мы отбрасываем одну из половин и соответствующим образом обновляем начальный и конечный индексы.
  5. Мы повторяем этот процесс до тех пор, пока не будет найдено целевое значение или интервал поиска не станет пустым.

Что ж, картинка стоит тысячи слов.

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

Анализ сложности бинарного поиска

Чтобы проанализировать временную сложность алгоритма бинарного поиска, нам нужно рассмотреть количество сравнений, необходимых для нахождения целевого значения. На каждой итерации мы уменьшаем интервал поиска вдвое, что приводит к временной сложности O(log n). Это означает, что время, необходимое для поиска элемента в наборе из n элементов, пропорционально log n.

Что касается пространственной сложности, алгоритм бинарного поиска имеет пространственную сложность O(1) для итеративной реализации и O(log n) для рекурсивной реализации. Рекурсивная реализация использует стек вызовов для хранения рекурсивных вызовов, что приводит к пространственной сложности O(log n).

Подведение итогов

Отличная работа по постижению основ бинарного поиска! Следует иметь в виду, что бинарный поиск действительно эффективен при работе с большими наборами данных. При работе с небольшими наборами данных более простой алгоритм, такой как for loop, может быть столь же эффективным или даже более быстрым, чем бинарный поиск.

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

Удачного кодирования. 👨🏻‍💻 До встречи в следующей статье! 👋