Algorithms and Data Structures · Middle · Question 13 of 75
What does this binary search return when target is not in the array?
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;
}- 1The index of the element closest in value to
target - 2
-1, which means the value wasn't found - ✓Correct answer: The index where
targetcould be inserted keeping the order
Explanation
This is lower bound: the first index whose value is >= target. If all values are smaller it returns arr.length. It's the basis of many variations: counting occurrences, finding ranges, inserting into a sorted array.