Base/Knowledges/IT/Алгоритмы/Поиск/Бинарный поиск (Binary search).md

#алгоритмы #поиск

! Эффективность O(n) = \log_2(n)

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

При бинарном поиске каждый раз исключается половина. В общем случае для списка из n элементов бинарный поиск выполняется за \log_{2}(n) шагов, тогда как простой поиск будет выполнен за n шагов.

Пример

const binarySearch = (list, item) => {
  let startIndex = 0;
  let endIndex = list.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);
    const candidate = list[midIndex];

    if (candidate === item) {
      console.log(`Item ${item} found at index ${midIndex}`);
      return midIndex;
    }

    if (candidate > item) {
      endIndex = midIndex - 1;
    } else {
      startIndex = midIndex + 1;
    }
  };

  console.log(`Not found "${item}"`);
  return null;
};

const list = [10, 20, 30, 50, 80, 100, 500];
binarySearch(list, 20); // 1
binarySearch(list, 40); // null

Источники:

• Адитья Бхаргава - Грокаем Алгоритмы