Lower-Bound and Upper-Bound Binary Search
Lower-bound and upper-bound binary search are the two primitives every other range query depends on. Lower-bound returns the first index where a value could be inserted; upper-bound returns the first index strictly greater than the value. This snippet covers both forms, then composes them to count occurrences in a sorted array in O(log n).
1,181 views
34
function lowerBound(arr, target) {
let lo = 0;
let hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
console.log(lowerBound([1, 2, 4, 4, 4, 6], 4)); // 2 (first 4)
console.log(lowerBound([1, 2, 4, 4, 4, 6], 5)); // 5 (insert before 6)
console.log(lowerBound([1, 2, 4, 4, 4, 6], 0)); // 0 (insert at start)
console.log(lowerBound([1, 2, 4, 4, 4, 6], 9)); // 6 (insert at end)Lower-bound returns the smallest index i such that arr[i] >= target. The half-open interval [lo, hi) and the arr[mid] < target test are the two pieces that distinguish it from a standard binary search: when the midpoint is too small, the target must live strictly to the right; otherwise the midpoint itself remains a candidate. The loop terminates with lo === hi, and that index is the answer. Time complexity is O(log n). This is the C++ std::lower_bound and Python bisect.bisect_left rewritten in JavaScript.
function upperBound(arr, target) {
let lo = 0;
let hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (arr[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
console.log(upperBound([1, 2, 4, 4, 4, 6], 4)); // 5 (first index > 4)
console.log(upperBound([1, 2, 4, 4, 4, 6], 5)); // 5 (same as lowerBound for non-present)
console.log(upperBound([1, 2, 4, 4, 4, 6], 6)); // 6 (past the end)Upper-bound is identical to lower-bound except the comparison is <= instead of <. That single change shifts the result from 'first index that is >= target' to 'first index strictly > target'. For values not present in the array, both functions return the same insertion point. The two together let you locate every occurrence of a value (and its multiplicity) in O(log n). The C++ analogue is std::upper_bound, the Python analogue is bisect.bisect_right.
function lowerBound(arr, t) { let lo = 0, hi = arr.length; while (lo < hi) { const m = (lo + hi) >>> 1; if (arr[m] < t) lo = m + 1; else hi = m; } return lo; }
function upperBound(arr, t) { let lo = 0, hi = arr.length; while (lo < hi) { const m = (lo + hi) >>> 1; if (arr[m] <= t) lo = m + 1; else hi = m; } return lo; }
function countOccurrences(arr, target) {
return upperBound(arr, target) - lowerBound(arr, target);
}
console.log(countOccurrences([1, 2, 4, 4, 4, 6], 4)); // 3
console.log(countOccurrences([1, 2, 4, 4, 4, 6], 5)); // 0
console.log(countOccurrences([1, 2, 4, 4, 4, 6], 6)); // 1Once you have both primitives, counting how many times a value appears in a sorted array reduces to subtracting their results. This pattern generalises to range queries: 'how many values fall in [a, b]' is upperBound(b) - lowerBound(a). Two log-n scans replace the linear pass a naive solution would do, which matters for repeated queries on a static sorted array. Pre-sort once, then answer each query in O(log n) with these two primitives.