Алгоритмы. Бинарный поиск.

Оглавление

Всем привет. Сегодня я хотел бы поговорить с вами на тему алгоритмов и как можно их применять на практике. Зачем знать алгоритмы? Любое приложение которые вы создаете или сайт со временем будет разрастаться и вам потребуется его оптимизировать. Для этого вам и потребуется те самые знание алгоритмов.

Поиск данных

Любое наше приложение имеет какой-то набор повторяющихся данных. Скорее всего ( и удобнее) данные будут хранится в массиве. Частой задачей стоящей перед разработчиком стоит поиск нужных данных в текущем массиве. Если у нас имеется небольшой набор данных то можно использовать обычный алгоритм для поиска ( линейный поиск ). Если таких данный много то наш поиск начнет «логать» пожирая большое количество ресурсов. Для решения этой задачи и был разработан бинарный поиск.

Логика

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

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

Условия

— Если оно меньше, мы можем удалить правую половину массива.
— Если оно больше, мы можем удалить левую половину массива.
— Если оно равно, мы возвращаем значение

Код


const binarySearch = (list, item) => {
    let low = 0;
    let high = list.length - 1;
 
    while (low <= high) { let mid = Math.floor((low + high) / (2)); 
		let guess = list[mid]; 
		if (guess === item) { 
			return guess; 
		} 
		if (guess > item) {
            high = mid - 1;
        }
 
        if (guess < item) {
            low = mid + 1;
        }
    }
 
    return null;
}
 
binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 8);