Algorytmy i struktury danych · Middle · Pytanie 13 z 75
Co zwróci to wyszukiwanie binarne, gdy target nie ma w tablicy?
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}- 1Indeks elementu najbliższego wartością do
target - 2
-1, co oznacza, że wartości nie znaleziono - ✓Poprawna odpowiedź: Indeks, pod który można wstawić
target, zachowując kolejność
Wyjaśnienie
To lower bound: pierwszy indeks z wartością >= target. Jeśli wszystkie wartości są mniejsze, zwraca arr.length. Na nim opiera się wiele wariantów: liczenie wystąpień, szukanie zakresów, wstawianie do posortowanej tablicy.