Определение
Двоичный поиск — это алгоритм поиска в отсортированном массиве путем многократного деления интервала поиска пополам. Идея двоичного поиска заключается в том, чтобы использовать информацию о том, что массив отсортирован, и уменьшить временную сложность до O(Log n).
Сравнение
Двоичный поиск в нотации Big O имеет сложность O(log n), по сравнению с линейным поиском, который имеет временную сложность O(n).
Двоичный поиск способен искать в отсортированных массивах гораздо быстрее, чем линейный поиск.
Пример из реальной жизни
Я думаю о числе от 1 до 50, ответ — 1.
Линейный поиск
Число = 50? Нет
Число = 49? Нет
…
Число = 2 ? Нет
Номер = 1 ? Да!
В худшем случае требуется 50 угадываний!
Бинарный поиск
Число = 25 ? Нет, меньше
Число = 12 ? Нет, меньше
Число = 6 ? Нет, меньше
Число = 3 ? Нет, меньше
Число = 2 ? Нет, меньше
Номер = 1 ? Да!
В худшем случае требуется 6 угадываний!
Вывод
Если предположить, что 1,000,000 чисел!
Линейный поиск приведет к 1,000,000 угадываний (в худшем случае)
Бинарный поиск приведет к 20 угадайкам (в худшем случае)
Визуализация
Бинарный поиск
Линейный поиск
Кодирование
const binarySearch = (sortedArr, value) => {
let left = 0;
let right = sortedArr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const midVal = sortedArr[mid];
if (midVal === value) {
return mid;
} else if (midVal < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};