LESSON 274 OF 415 · BINARY SEARCH

Lower Bound in Swift: O(log n) Binary Search

Practice O(log n) Read the full explanation

Given a sorted array of integers nums, find the smallest index where we can place a given value such that the array remains sorted

Example 1:

Input: nums = [1, 2, 3, 5, 7], value = 4
Output: 3
Explanation: Placing the value 4 at index 3 we obtain nums = [1, 2, 3, 4, 5, 7]

Example 2:

Input: nums = [1, 2, 3], value = 2
Output: 1
Explanation: Placing the value 2 at index 1 we obtain nums = [1, 2, 2, 3]

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Lower Bound in Swift, explained

Problem overview

The method lowerBound receives a sorted array of integers, nums, and a number value. It returns the smallest index where value could be inserted so that the array stays sorted. Equivalently, it returns the index of the first element that is not less than value.

With 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]. With nums = [1, 2, 3] and value = 2, the answer is 1, not 2, because the 2 already in the array sits at index 1 and the new 2 may go in front of it. The statement asks for O(log n) time and O(1) extra space.

Approach: binary search for the first element that is not smaller

A linear scan would walk from the left until it meets an element that is at least value. That is O(n). Because the array is sorted, the elements smaller than value form a prefix, and the rest form a suffix. The answer is the border between them, and a border in sorted data can be found by repeatedly halving the search window.

Look at the element in the middle of the window:

If it is smaller than value, then it and everything to its left are smaller too. The border lies to the right, so the window shrinks to the part after the middle.
Otherwise it is at least value. It might be the first such element, or the first one might lie further left. Either way the border is at the middle or to its left, so the window shrinks to the part before the middle.

When the window is empty, the left edge has crossed the border and points at the first element that is not smaller, or just past the end if there is none.

Step by step

Declare left and right with var, since both move. They start at the first index, 0, and the last index, nums.count - 1, so the window covers the whole array.
Loop while left <= right. Using <= keeps the loop running when the window holds a single element, which could still be the answer.
Compute middle as (left + right) / 2 with let. Integer division rounds down, so it is always a valid index inside the window.
If nums[middle] < value, move left to middle + 1. No index up to middle can be the answer.
Otherwise move right to middle - 1. The element at middle is at least value, so the answer is further left, or middle itself, which the final left will still point at.
Return left after the loop. It ends one step past the last element known to be smaller than value.

The solution in Swift

class Solution {
    func lowerBound(_ nums: [Int], _ value: Int) -> Int {
        var left = 0, right = nums.count - 1
        while left <= right {
            let middle = (left + right) / 2
            if nums[middle] < value {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return left
    }
}

The Swift details worth a closer look:

Two variables, one var. var left = 0, right = nums.count - 1 declares both at once. Both are mutable, which is why they use var, while middle is a new constant on every pass and uses let.
Integer division. Dividing two Int values gives an Int and drops the fraction, so no conversion is needed to get a usable index.
The _ labels. Each parameter has _ before its name, so the call is lowerBound(nums, value) with no argument labels.
Overflow is a trap in Swift. Int is 64 bits, and an arithmetic overflow stops the program instead of wrapping. The sum left + right of two array indices never gets near that limit, so (left + right) / 2 is safe here. The form left + (right - left) / 2 gives the same midpoint without ever adding the two indices, and is a good habit.
An empty array works. nums.count - 1 is -1, so the loop condition 0 <= -1 is false and the method returns 0 straight away.

Complexity

Time: O(log n). Each iteration discards at least half of the window, so after about log2(n) iterations it is empty. An array of a million elements needs at most around 20 iterations.

Space: O(1). The method keeps three integers and never copies the array.

Edge cases and common mistakes

Value larger than everything. For [1, 2, 3] and 10, the method returns 3, which is nums.count. That index is one past the end, and it is the correct insertion point.
Value smaller than everything. For [1, 2, 3] and -4 the result is 0.
Duplicates. For [1, 2, 2, 2, 3] and 2 the result is 1, the first of the equal elements. That is why equal elements go to the else branch: moving right left of an equal element keeps searching for an earlier one.
Returning on equality. Stopping the moment nums[middle] == value would return any of the equal elements, not the first.
Using < in the loop condition. With left < right, a window of one element is never examined. For [5] and 6 the loop would not run at all and the method would return 0 instead of 1.
Returning right. After the loop right is left - 1, the last element that is smaller than value, not the insertion point.

Testing

nums = [1, 2, 3, 5, 7], value = 4 gives 3.
nums = [1, 2, 3], value = 2 gives 1.
nums = [1, 2, 2, 2, 3], value = 2 gives 1.
nums = [1, 2, 3], value = 10 gives 3.
nums = [], value = 5 gives 0.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free