Бинарный поиск в JavaScript: принципы работы и примеры использования

Бинарный поиск (Binary Search) это эффективный алгоритм для поиска значения в отсортированном массиве. Он работает следующим образом:

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

Пример функции бинарного поиска в JavaScript:

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let currentElement = array[mid];

    if (currentElement === target) {
      return mid;
    }
    else if (target < currentElement) {
      right = mid - 1;
    }
    else {
      left = mid + 1;
    }
  }
  
  return -1;
}

1. left и right – это границы массива, которые мы просматриваем в данный момент.
2. mid – это индекс элемента в середине массива, мы используем его для определения, в какую сторону двигаться дальше.
3. currentElement – это элемент в массиве, который сейчас проверяется.
4. if (currentElement === target) – если текущий элемент равен искомому значению, то возвращаем его индекс.
5. else if (target < currentElement) – если искомое значение меньше текущего элемента, то мы перемещаем правую границу влево, так как искомое значение должно находиться слева от текущего элемента.
6. else – в противном случае, если искомое значение больше текущего элемента, мы перемещаем левую границу вправо, так как искомое значение должно находиться справа от текущего элемента.
7. while (left <= right) – цикл повторяется, пока левая граница меньше или равна правой.
8. return -1 – если мы вышли из цикла и не нашли искомое значение, то возвращаем -1, что означает, что элемент не найден.

Вот пример использования функции бинарного поиска:

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 5;

const index = binarySearch(array, target);

console.log(index); // Output: 4

1. Создаем массив array с данными, в котором будем искать элемент.
2. Задаем значение target, которое мы хотим найти.
3. Вызываем функцию binarySearch с передачей массива и искомого значения.
4. Результат вызова функции присваиваем переменной index.
5. Выводим index в консоль.

Результатом будет индекс 4, так как элемент со значением 5 находится под индексом 4 в массиве.

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