Оглавление
Всем привет. Сегодня я хотел бы поговорить с вами на тему алгоритмов и как можно их применять на практике. Зачем знать алгоритмы? Любое приложение которые вы создаете или сайт со временем будет разрастаться и вам потребуется его оптимизировать. Для этого вам и потребуется те самые знание алгоритмов.
Поиск данных
Любое наше приложение имеет какой-то набор повторяющихся данных. Скорее всего ( и удобнее) данные будут хранится в массиве. Частой задачей стоящей перед разработчиком стоит поиск нужных данных в текущем массиве. Если у нас имеется небольшой набор данных то можно использовать обычный алгоритм для поиска ( линейный поиск ). Если таких данный много то наш поиск начнет «логать» пожирая большое количество ресурсов. Для решения этой задачи и был разработан бинарный поиск.
Логика
Основная суть логики работы бинарного поиска заключена в разбиение отсортированного массива на две части ( очень важно что бы массив был отсортирован, в противном случае алгоритм не будет работать ).
Значение которое мы ищем сравнивается с массивом и проверяется: больше, меньше или равно данное значение. В результате чего кусок массива который не подходит по условию просто отсекается. В результате мы получаем меньший массив с которым продолжаем нашу проверку до момента нахождения нужного значения.
Условия
— Если оно меньше, мы можем удалить правую половину массива.
— Если оно больше, мы можем удалить левую половину массива.
— Если оно равно, мы возвращаем значение
Код
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);
Заключение
Сегодня и попытался изложить основную суть бинарного поиска. Надеюсь что данная статья была вам полезна. Удачно покодить!)
Комментарии: