Алгоритми та структури даних · Middle · Запитання 13 з 75
Що поверне цей бінарний пошук, якщо target немає в масиві?
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;
}- 1Індекс елемента, найближчого за значенням до
target - 2
-1, що означає «значення не знайдено» - ✓Правильна відповідь: Індекс, куди можна вставити
targetзі збереженням порядку
Пояснення
Це lower bound: перший індекс зі значенням >= target. Якщо всі значення менші, повертається arr.length. На цьому побудовано багато варіацій: підрахунок входжень, пошук діапазонів, вставка у відсортований масив.