Problem overview
The function lowerBound receives a sorted IntArray called nums and an integer value. It returns the smallest index at which value could be inserted so that the array stays sorted. This index is called the lower bound: the first position whose element is not smaller than value.
In the first example, nums = [1, 2, 3, 5, 7] and value = 4. Inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7], so the answer is 3. In the second, nums = [1, 2, 3] and value = 2. The value 2 is already at index 1, and inserting another one there gives [1, 2, 2, 3], so the answer is 1, the first of the equal elements.
The statement asks for O(log n) time and O(1) extra space.
Approach: binary search that never stops early
A linear scan would walk from the start until it meets an element that is at least value, which is O(n). Because the array is sorted, the elements smaller than value form a prefix, and everything after it is at least value. The answer is the boundary between the two parts, and binary search finds a boundary in O(log n).
This differs from an ordinary search for a value, which returns as soon as it hits an equal element. Here an equal element isn't the end: there might be another equal one to its left, and the answer is the leftmost position. So the loop never returns from inside. It keeps narrowing the range with two rules:
- If
nums[middle] < value, then the middle and everything to its left are too small to be the answer, so movelefttomiddle + 1. - Otherwise
nums[middle]is at leastvalue, so the answer ismiddleor something further left. Moverighttomiddle - 1.
When the range is empty, left has stopped on the first element that is at least value. Every index before left held something smaller, and every index from left on was never moved past, so it is at least value. If all elements are smaller, left ends at nums.size, one past the last index, which is exactly where the value would be appended.
On [1, 2, 3, 5, 7] with value = 4: the range is 0 to 4, the middle index is 2, and 3 is smaller than 4, so left becomes 3. The range is 3 to 4, the middle index is 3, and 5 is not smaller than 4, so right becomes 2. Now left (3) is greater than right (2), the loop ends, and the function returns 3.
Step by step
- Set the bounds.
leftis 0 andrightisnums.size - 1, each on its own line. Both arevar, since both move. - Loop while the window is non-empty. The condition is
left <= right, so the window can shrink to a single element before it disappears. - Take the middle.
middleis avalequal to(left + right) / 2. Integer division rounds down, so it is always a valid index. - Discard the left side. If
nums[middle] < value, setleft = middle + 1. - Otherwise discard the right side. Set
right = middle - 1. The middle element itself is at leastvalue, but it is dropped from the window without being recorded. This is safe because the loop ends withleftsitting just afterright, on the first element that is not smaller thanvalue. - Return
left.
The solution in Kotlin
class Solution {
fun lowerBound(nums: IntArray, value: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val middle = (left + right) / 2
if (nums[middle] < value) {
left = middle + 1
} else {
right = middle - 1
}
}
return left
}
}
Kotlin details:
- An
Intdivision truncates. Sinceleftandrightare never negative while the loop runs,(left + right) / 2rounds down. Intis 32 bits and wraps silently on overflow, soleft + rightcould in theory exceed the range. It only happens for arrays with more than a billion elements;left + (right - left) / 2avoids it, and the lesson's simpler form is fine at normal sizes.- There is no
returninside the loop. Every path through it moves a bound, and the singlereturn leftafter the loop gives the answer. - For an empty array,
rightis-1, the loop doesn't run, and the function returns 0.
Complexity
Time is O(log n): each pass cuts the window roughly in half, so there are about log₂(n) passes. Space is O(1), since only a few integers are kept.
Edge cases and common mistakes
- Value larger than everything.
[1, 2, 3]withvalue = 9returns 3, which equalsnums.size. - Value smaller than everything.
[1, 2, 3]withvalue = 0returns 0. - Empty array. The result is 0.
- Several equal elements. For
[1, 2, 2, 2, 3]withvalue = 2, the function returns 1, the first 2, and not 2 or 3. Returning early on a match, as plain binary search does, can land on a later copy. - Using
<=in the comparison. Withnums[middle] <= value, the function returns the position after the last equal element, which is a different quantity (the upper bound). - Returning
rightinstead ofleft. At the endrightis one before the answer.
Testing
[1, 2, 3, 5, 7]withvalue = 4returns3.[1, 2, 3]withvalue = 2returns1.[1, 2, 3]withvalue = 9returns3.[]withvalue = 9returns0.