Вы устали просматривать длинный несортированный список в поисках определенного элемента? Что ж, тебе повезло! Сегодня мы обсудим алгоритм бинарного поиска, который представляет собой метод быстрого и эффективного поиска определенного элемента в отсортированном списке.

Во-первых, давайте поговорим о том, что такое отсортированный список. Отсортированный список — это набор элементов, которые расположены в порядке возрастания или убывания. Например, допустим, у нас есть список чисел: 2, 4, 7, 9, 12, 16, 20. Это отсортированный список в порядке возрастания. Если бы мы искали число 7 в этом списке, используя линейный поиск (также известный как последовательный поиск), нам пришлось бы начинать с начала списка и сравнивать каждый элемент с искомым числом, пока мы не получим Найди это. В этом случае нам пришлось бы просмотреть четыре элемента, прежде чем найти 7.

Это может занять очень много времени, особенно если мы имеем дело с большим списком. Здесь на помощь приходит алгоритм бинарного поиска. Алгоритм бинарного поиска — это алгоритм «разделяй и властвуй», который может быстро найти определенный элемент в отсортированном списке. Он работает путем многократного деления списка пополам до тех пор, пока элемент не будет найден или определен как отсутствующий в списке.

Вот как это работает:

  1. Начните с определения середины списка. Это можно сделать, сложив первый и последний индекс списка вместе и разделив на два.
  2. Сравните среднее значение с элементом, который вы ищете.
  3. Если значение средней точки равно элементу, который вы ищете, то все готово! Возвращает индекс элемента.
  4. Если среднее значение больше, чем искомый элемент, повторите поиск в левой половине списка.
  5. Если среднее значение меньше элемента, который вы ищете, повторите поиск в правой половине списка.

Используя наш предыдущий пример, предположим, что мы ищем число 7. Мы начнем с поиска середины списка, которая равна 9. Поскольку 9 больше 7, мы знаем, что число 7 должно быть в левой половине. списка. Затем мы повторили бы поиск в левой половине списка, то есть 2, 4, 7. Мы нашли наш элемент всего за два шага!

Теперь, когда у нас есть общее представление о том, как работает алгоритм бинарного поиска, давайте посмотрим, как мы можем реализовать его в JavaScript. Вот простой пример:

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

  while (left <= right) {
    let 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;
}

let arr = [1, 3, 7, 9, 12, 16, 20];
let target = 7;

console.log(binarySearch(arr, target)); // output: 2

Затем мы определяем две переменные, левую и правую, которые представляют левый и правый индексы массива. Первоначально левый индекс установлен на 0, а правый индекс установлен на последний индекс массива.

Затем мы вводим цикл while, который продолжается до тех пор, пока левый индекс меньше или равен правому индексу. Внутри цикла мы вычисляем средний индекс массива, усредняя левый и правый индексы и округляя в меньшую сторону с помощью Math.floor.

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

Мы продолжаем этот процесс, пока либо не найдем целевое значение, либо не определим, что его нет в массиве. Если мы выходим из цикла while, не найдя целевого значения, мы возвращаем -1, чтобы указать, что его нет в массиве.

Давайте посмотрим на алгоритм бинарного поиска в действии на нескольких примерах:

Пример 1:

const arr = [2, 4, 6, 8, 10];
console.log(binarySearch(arr, 8)); // Output: 3

В этом примере мы ищем значение 8 в массиве [2, 4, 6, 8, 10]. Алгоритм сначала проверяет средний индекс, равный 2 (помните, мы округляем в меньшую сторону). Поскольку значение по индексу 2 меньше нашего целевого значения 8, мы знаем, что целевое значение может находиться только в правой половине массива. Мы обновляем левый индекс, чтобы он был на единицу больше, чем средний индекс, что устанавливает его равным 3. Затем мы пересчитываем средний индекс, который теперь равен 4. Поскольку значение в индексе 4 равно нашему целевому значению, мы возвращаем 4.

Пример 2:

const arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 6)); // Output: -1
In this example, we’re searching for the value 6 in the array [1, 3, 5, 7, 9]. The algorithm first checks the middle index, which is 2 (since we round down). Since the value at index 2 is less than our target value of 6, we know that the target value can only be in the right half of the array. We update the left index to be one more than the middle index, which sets it to 3. We then recalculate the middle index, which is now 4. Since the value at index 4 is greater than our target value, we know that the target value can only be in the left half of the array. We update the right index to be one less than the middle index, which sets it to 3. We then recalculate the middle index, which is still 3. Since the value at index 3 is not equal to our target value of 6, we exit the while loop and return -1 to indicate that the target value is not in the array.

В этом примере мы ищем значение 6 в массиве [1, 3, 5, 7, 9]. Алгоритм сначала проверяет средний индекс, который равен 2 (поскольку мы округляем в меньшую сторону). Поскольку значение по индексу 2 меньше нашего целевого значения 6, мы знаем, что целевое значение может находиться только в правой половине массива. Мы обновляем левый индекс, чтобы он был на единицу больше, чем средний индекс, что устанавливает его равным 3. Затем мы пересчитываем средний индекс, который теперь равен 4. Поскольку значение в индексе 4 больше, чем наше целевое значение, мы знаем, что целевое значение value может находиться только в левой половине массива. Мы обновляем правый индекс, чтобы он был на единицу меньше, чем средний индекс, что устанавливает его равным 3. Затем мы пересчитываем средний индекс, который по-прежнему равен 3. Поскольку значение в индексе 3 не равно нашему целевому значению 6, мы выходим цикл while и вернуть -1, чтобы указать, что целевое значение не находится в массиве.

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

  1. Поиск в базах данных. Двоичный поиск обычно используется в системах баз данных для быстрого поиска в больших объемах данных.
  2. Проверка орфографии: Двоичный поиск используется в алгоритмах проверки орфографии, чтобы предложить исправления слов с ошибками.
  3. Алгоритмы сортировки. Двоичный поиск можно использовать как часть различных алгоритмов сортировки, таких как быстрая сортировка и сортировка слиянием.
  4. Разработка игр: Двоичный поиск используется в разработке игр для поиска врагов, предметов или других элементов игры, которые находятся в пределах определенного диапазона.
  5. Сетевая маршрутизация. Двоичный поиск можно использовать для эффективного поиска наилучшего сетевого маршрута между двумя точками.
  6. Генетические исследования: бинарный поиск используется в генетических исследованиях для поиска определенных генетических последовательностей в больших наборах данных.
  7. Машинное обучение: бинарный поиск используется в алгоритмах машинного обучения для поиска оптимальных значений параметров модели.

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

Спасибо за чтение! Пожалуйста, дайте мне знать, что вы хотите видеть новые главы и подпишитесь, чтобы не пропустить выход новой статьи :)