Бинарный поиск работает только по отсортированному массиву, зато невероятно быстр. Идея: каждый раз сравниваем искомое со средним элементом и отбрасываем половину диапазона.
function binarySearch(arr, target) { let low = 0, high = arr.length - 1; while (low <= high) { const mid = Math.floor((low + high) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) low = mid + 1; // искомое правее else high = mid - 1; // искомое левее } return -1; }
Сложность — O(log n). Это огромный выигрыш: в массиве из миллиона элементов линейный поиск может потребовать миллион проверок, а бинарный — всего около 20 (так как 2²⁰ ≈ миллион).
Аналогия — поиск слова в словаре: вы не листаете подряд, а открываете примерно посередине и сразу понимаете, в какой половине искать дальше. Цена скорости — массив должен быть отсортирован. Если он меняется редко, а ищут часто, бинарный поиск окупается многократно.