Бинарный поиск на JavaScript

Бинарный поиск на JavaScript

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

Это невероятно эффективный подход, где количество шагов для поиска нужного элемента не превышает logn. При классическом переборе же для поиска нужного элемента в худшем случае придется проверить весь массив.

Как работает бинарный поиск?

Суть бинарного поиска в том, что на каждом шаге мы исключаем ровно половину чисел в массиве. Что это значит?

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

В простом представлении это можно выразить так: у нас есть массив из 5 чисел - от 1 до 6.

Размер массива в этом случае будет равен 6. Загадаем, что нам нужно найти число 2. Сколько шагов потребуется?

На первом шаге будем проверять середину массива или число 3. Оно больше, чем нужно. Значит вторым шагом будем искать уже от 0 (начала массива), до 3 (середины массива из прошлого шага).

Середина нового отрезка 1,5 - с округлением 1. Проверяем его - оно меньше чем нужно, значит сдвигаем нижнюю границу до 2.

Проверяем следующий отрезок от 2 до 3 - середина с округлением 2. Это как раз то число, которое мы загадали. Этот упрощенный пример использовал максимальное количество попыток для поиска в искомом массиве - 3.

Повторюсь, что текстовый пример был сильно упрощен для понимания принципа работы поиска, давайте посмотрим на функцию бинарного поиска, которую я написал на языке JavaScript

const binarySearch = (array, item) => {
	let low = 0;
	let high = array.length - 1;
 
  while(low <= high) {
  	let middle = parseInt((high + low) / 2);
	let value = array[middle];
 
  	if (value === item) {
		return value;
    }
 
    if (value > item) {
    	high = middle - 1;
    } else {
    	low = middle + 1;
    }
  }
 
  return null;
};
 
const array = [1, 2, 3, 4, 5, 6];
const item = 2;
 
binarySearch(array, item);

Ничего сложного тут нет, остановимся лишь на нескольких моментах:

Ищем от первого элемента (индекс 0 в массиве) до последнего (индекс длина массива минус 1).

Сразу проверим, что середина массива не является нужным элементом - это нам может сократить время поиска.

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

В противном случае сдвинем нижнюю границу на +1 от середины.

Если ничего не найдено функция вернет null.

24.03.19
Для просмотра сайта обновите браузер.