Problem overview
The method lowerBound receives a sorted array of integers, nums, and a value. It returns the smallest index at which value could be inserted so that the array stays sorted. Equivalently, it is the index of the first element that is not less than value, or nums.length if 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 already exists at index 1, and inserting at the earliest valid place puts the new 2 in front of the old one.
Approach: binary search that keeps going after a match
The statement asks for O(log n) time and O(1) extra space, so a left-to-right scan for the first element that is large enough, which is O(n), is too slow. The array is sorted, which is what binary search needs.
Ordinary binary search stops at a match. Here you want the first position that qualifies, so you never stop early. Each step looks at the middle element and asks one question: is it smaller than value?
- If yes, the middle element and everything before it are too small to be the answer. Move
leftpastmiddle. - If no, the middle element is at least
value, so it could be the answer, but something earlier might also be. Moverightto just beforemiddleand keep looking on the left.
The loop runs until the range is empty. At that point, right is one less than left. Every index below left holds a value smaller than value, and every index from left on holds a value that is at least value. So left is the first index of the second kind, which is the answer.
On [1, 2, 3, 5, 7] with value = 4: left = 0, right = 4, middle = 2, and nums[2] = 3 is smaller, so left = 3. Next middle = 3, and nums[3] = 5 is not smaller, so right = 2. Now left > right, and the answer is left = 3.
Step by step
- Set the window.
leftandrightare declared in onelet, starting at0andnums.length - 1, so the window covers the whole array. - Loop while the window is not empty. The condition is
left <= right. With<=, a window of one element is still examined. - Compute the middle.
Math.floor((left + right) / 2). Division of numbers can produce a fraction, as in3 / 2, and an index must be whole. - Too small? If
nums[middle] < value, the answer is to the right, soleft = middle + 1. - Otherwise, the middle element is at least
value, so the answer ismiddleor somewhere to its left:right = middle - 1. - Return
left. It is the first index whose value is at leastvalue.
The solution in TypeScript
class Solution {
lowerBound(nums: number[], value: number): number {
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;
}
}- One
let, two variables.let left = 0, right = nums.length - 1;declares both. Each is inferred asnumber. Math.floorinstead of integer division. There is no integer division operator.7 / 2is3.5, so the result must be rounded down explicitly.- No overflow worry.
left + rightis an ordinary double sum, and array indices are far below the point where doubles lose precision. - The return value can be
nums.length. When every element is smaller,leftends one past the last index. That is a valid insertion position, though not a valid index to read. - Types are checked at compile time only. A sorted array is not something
number[]can express. On unsorted data the method returns an answer with no meaning.
Using the result, and the upper-bound twin
The returned index is exactly where Array.prototype.splice should insert the value. After nums.splice(lowerBound(nums, 4), 0, 4) on [1, 2, 3, 5, 7], the array is [1, 2, 3, 4, 5, 7]. The middle argument 0 means "remove nothing", and splice itself moves the later elements, so that step costs O(n) even though finding the position was O(log n).
Changing one comparison gives the related function that finds the position after the last equal element:
function upperBound(nums: number[], value: number): number {
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;
}On [1, 2, 2, 2, 3] with 2 it returns 4, while lowerBound returns 1. The difference between the two answers, 4 - 1 = 3, is how many times the value occurs.
Complexity
Time: O(log n). Each iteration discards at least half of the window, so the loop runs at most about log₂(n) + 1 times.
Space: O(1). Only left, right and middle are stored.
Edge cases and common mistakes
- Empty array.
rightis-1, the loop does not run and the answer is0. - Value smaller than everything.
[1, 2, 3]with0gives0. - Value larger than everything.
[1, 2, 3]with9gives3, which equals the length. - Duplicates.
[1, 2, 2, 2, 3]with2gives1, the first copy. Returning at the first match would give an index in the middle of the run, which is wrong for this problem. - Using
<=in the comparison.nums[middle] <= valuefinds the position after the last equal element, a different function often called the upper bound. - Returning
right. It ends one position too low. The answer isleft. - Skipping
Math.floor. A fractional index such as1.5readsundefinedfrom the array.
Testing
nums = [1, 2, 3, 5, 7],value = 4gives3.nums = [1, 2, 3],value = 2gives1.nums = [1, 2, 3],value = 0gives0.nums = [1, 2, 3],value = 9gives3.nums = [],value = 5gives0.