Problem overview
The method lowerBound receives a sorted Array[Int] named nums and an Int named value. 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.
In the first example, nums = [1, 2, 3, 5, 7] and value = 4. The elements 1, 2 and 3 are smaller than 4, and 5 is the first one that isn't, so the answer is index 3. In the second example, nums = [1, 2, 3] and value = 2. The value is already present at index 1, and inserting it there is still valid, so the answer is 1 and not 2.
If every element is smaller than value, the answer is nums.length, one past the last index. If value is at most the first element, the answer is 0.
Approach: binary search on the boundary
A linear scan from the left would find the first element that is at least value in O(n) time. The statement asks for O(log n) time and O(1) extra space, so the scan has to go.
The array is sorted, so the elements split into two groups: a (possibly empty) prefix of elements smaller than value, followed by a suffix of elements that are at least value. The answer is the position where the prefix ends. Looking at one element tells you which group it belongs to, and that lets you discard half of the candidates, the same trick binary search uses to find an exact value.
The loop keeps a window [left, right] and maintains two facts:
- every index before
leftholds a value smaller thanvalue; - every index after
rightholds a value that is at leastvalue.
The window starts as the whole array, where both facts hold trivially. Each iteration shrinks the window while keeping both facts true. When the window is empty, right is exactly left - 1, so the two facts together say that left is the first index of the "at least value" group.
Step by step
- Declare
leftandrightwithvar, because both move. They start at0andnums.length - 1. - Loop while
left <= right. Using<=instead of<matters: a window holding a single element still has to be examined. - Compute
middleas(left + right) / 2. Dividing twoInts discards the fraction, somiddleis a valid index inside the window. - If
nums(middle) < value, thenmiddleand everything to its left is too small. Setleft = middle + 1. - Otherwise
nums(middle)is at leastvalue, so the answer ismiddleor something to its left. Setright = middle - 1. Indexmiddleis not lost: it satisfies the second fact, and when the search endsleftwill point at it unless an even smaller index also qualifies. - After the loop,
leftis the answer.
The solution in Scala
class Solution {
def lowerBound(nums: Array[Int], value: Int): Int = {
var left = 0
var right = nums.length - 1
while (left <= right) {
val middle = (left + right) / 2
if (nums(middle) < value) {
left = middle + 1
} else {
right = middle - 1
}
}
left
}
}
Scala details
Arrays are indexed with parentheses, nums(middle), not square brackets. Square brackets in Scala hold type parameters, as in Array[Int].
The last expression of a block is its value, so the method ends with a bare left and needs no return. The if/else inside the loop is used only for its side effects, which is fine: both branches assign to a var.
Method parameters are vals and can't be reassigned, which is why the search uses its own var variables. The midpoint is a val, because each iteration creates a fresh one.
An Int is 32 bits and overflow wraps silently. For (left + right) / 2 to go wrong, the sum of two indices would have to exceed 2,147,483,647, which needs an array of more than a billion elements. The safer form left + (right - left) / 2 never adds the two indices, and it costs nothing, so it is a good habit. For example, with left = 2147483636 and right = 2147483646, the expression (left + right) / 2 evaluates to -7, while left + (right - left) / 2 gives 2147483641.
Complexity
Each iteration discards at least half of the window, so the loop runs at most about log n times (base 2, plus one) and the time is O(log n). The method stores only three Ints, so the extra space is O(1).
Edge cases and common mistakes
- Value larger than everything.
lowerBound(Array(1, 2, 3), 9)returns 3, which isnums.length. Callers must treat that as "no element at or abovevalue", not as a valid index. - Value smaller than everything.
lowerBound(Array(1, 2, 3), 0)returns 0. - Empty array.
rightstarts at-1, the loop never runs, and the method returns 0. - Duplicates.
lowerBound(Array(1, 2, 2, 2, 3), 2)returns 1, the first of the equal elements. This is why the comparison is strict (<) and equal elements fall into theelsebranch: whennums(middle)equalsvalue, the search keeps looking to the left for an earlier copy. - Returning on a match. Stopping as soon as
nums(middle) == valueis correct for plain binary search but wrong here, because an equal element may not be the first one. - Off-by-one updates. Setting
left = middleorright = middleinstead of moving pastmiddlecan make the window stop shrinking, and the loop never ends.
Testing
Try these inputs in the editor above:
[1, 2, 3, 5, 7]withvalue = 4gives 3.[1, 2, 3]withvalue = 2gives 1.[1, 2, 2, 2, 3]withvalue = 2gives 1.[1, 2, 3]withvalue = 9gives 3.
