Create Next App

Бинарный поиск (Binary Search)

Ищет значение в отсортированном по возрастанию массиве. Поддерживает диапазон [low, high], на каждом шаге берёт серединуmid и сравнивает arr[mid] с target: при > сдвигает правую границу, при< – левую, при === – возвращает индекс. Останавливается, когда low > high (элемент отсутствует).

Сложность:

Время – O(log n), Память – O(1)

binary-search.ts

1function binarySearch(arr: number[], target: number): number {
2    let low = 0, high = arr.length - 1;
3    while (low <= high) {
4        const mid = Math.floor((low + high) / 2);
5        const guess = arr[mid];
6        if (guess === target) return mid;
7        if (guess > target) high = mid - 1; else low = mid + 1;
8    }
9    return -1;
10}
11
12const myList = [11,33,55,77,99];
13binarySearch(myList, 11) // index -> 0
14binarySearch(myList, 33) // index -> 1
15binarySearch(myList, 99) // index -> 4
16binarySearch(myList, 42) // index -> -1
17