Problem overview
The method lowerBound(nums, value) receives a sorted array and a number. It returns the smallest index at which value could be inserted while keeping the array sorted. Equivalently, it returns the index of the first element that is not less than value, or nums.length when every element is smaller.
For nums = [1, 2, 3, 5, 7] and value = 4, the answer is 3: inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7]. For nums = [1, 2, 3] and value = 2, the answer is 1. The value 2 is already there, and the smallest valid insertion index is the one in front of the existing 2.
The lesson asks for O(log n) time and O(1) extra space. This function is known as lower bound, and it is the building block behind "find the first position where a condition holds" in a sorted array.
Approach: binary search for the first element that is not smaller
A linear scan from the left finds the first element that is at least value in O(n) time. That ignores the one useful fact: the array is sorted. If the middle element is smaller than value, everything to its left is smaller too, so none of those indices can be the answer. If the middle element is at least value, it could be the answer, but nothing to its right can be better.
So each comparison throws away half of the remaining range, and the search needs about log₂ n comparisons. Searching a million elements takes around 20 steps.
The variables left and right mark the part of the array that might still hold the answer. A useful way to see the loop is as an invariant: everything before left is smaller than value, and everything after right is at least value. The range between them shrinks until it is empty, and at that point left sits exactly on the boundary.
Step by step
- Set the window.
left = 0andright = nums.length - 1, declared with onelet, cover the whole array. - Loop while
left <= right. Using<=lets the window shrink to a single element before it becomes empty. - Take the middle.
Math.floor((left + right) / 2). In JavaScript,/can produce a fraction: withleft + right = 3the quotient is 1.5, which is not an index.Math.floorrounds it down. - If
nums[middle] < value, the answer is to the right ofmiddle, so setleft = middle + 1. - Otherwise,
nums[middle]is at leastvalue, so the answer ismiddleor something before it. Setright = middle - 1. - Return
left. When the loop ends,rightequalsleft - 1, andleftis the first index whose value is at leastvalue. If every element is smaller thanvalue,leftends atnums.length, one past the last index.
The solution in JavaScript
class Solution {
lowerBound(nums, value) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (nums[middle] < value) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return left;
}
}
Trace for nums = [1, 2, 3, 5, 7] and value = 4:
left | right | middle | nums[middle] | Action |
|---|---|---|---|---|
| 0 | 4 | 2 | 3 | 3 < 4, so left = 3 |
| 3 | 4 | 3 | 5 | 5 is not < 4, so right = 2 |
Now left = 3 is greater than right = 2, the loop stops, and the method returns 3.
JavaScript details
- Integer division. JavaScript has no integer division operator.
Math.floor(x / 2)works for non-negative sums, and(left + right) >> 1is a common shorthand. Both are fine here. - Midpoint overflow. Languages with 32-bit integers sometimes compute
left + (right - left) / 2to avoid overflow. JavaScript numbers are doubles, andleft + rightis exact up to 2^53, far beyond any array length, so the simple form is safe. - Reading past the array. The loop never reads
nums[middle]outside the array, becausemiddlealways lies betweenleftandright, and those stay inside the valid range whileleft <= right.
The upper bound
The matching function, upper bound, returns the first index whose element is greater than value. Only the comparison changes, from < to <=:
function upperBound(nums, value) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (nums[middle] <= value) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return left;
}
For [1, 2, 2, 2, 3] and value = 2, the lower bound is 1 and the upper bound is 4, so upperBound - lowerBound is 3, the number of 2s.
Complexity
- Time:
O(log n). The window halves on every pass. - Space:
O(1). Three integer variables, no recursion.
Edge cases and common mistakes
- Value smaller than everything.
[1, 2, 3]with value 0 returns 0. - Value larger than everything.
[1, 2, 3]with value 9 returns 3, which isnums.lengthand not a valid index for reading. Check it before using the result asnums[index]. - Empty array.
rightstarts at -1, the loop doesn't run, and the method returns 0. - Duplicates. The method returns the first of equal elements, because an equal middle moves
rightto the left. That is what separates it from a search that stops at any match. - Returning
middleon a match. That would find some matching index, not the smallest one. - Using
left < right. The loop can then end before the last candidate is examined, and the result is off by one. - Returning
right. It ends atleft - 1, the last element smaller thanvalue(or -1), not the insertion index.
Testing
[1, 2, 3, 5, 7], value 4 gives 3.[1, 2, 3], value 2 gives 1.[1, 2, 2, 2, 3], value 2 gives 1.[1, 2, 3], value 9 gives 3.[], value 5 gives 0.
