Start learning free

LESSON 245 OF 338 · BINARY SEARCH

Lower Bound in Go: O(log n) Binary Search for an Insert Position

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 on the 4th index 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 on the 1st index 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
    Ctrl + Enter to check

    GO · BINARY SEARCH

    Lower Bound in Go, explained

    Problem overview

    The function lowerBound receives a sorted slice of integers, nums, and a value. It returns the smallest index at which value can be inserted while keeping the slice sorted. Equivalently, it is the index of the first element that is not smaller than value.

    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, not 2, because the smallest valid position is in front of the existing 2.

    The statement asks for O(log n) time and O(1) extra space, so a left-to-right scan is too slow and the function must use binary search.

    Approach: binary search for the boundary

    Think of the sorted slice as two parts: the elements smaller than value come first, and the elements that are at least value come after them. The answer is the index where the second part begins. Because the slice is sorted, "is this element smaller than value?" is true for a prefix and false for the rest, which is exactly the shape binary search can handle.

    Look at the middle element. If it is smaller than value, then it and everything before it belong to the first part, so the boundary lies to its right. If it is at least value, then it could be the first element of the second part, or the boundary could be further left. Either way, half of the range is dropped each time.

    Unlike an ordinary search, this one doesn't stop when it sees an equal element. An equal element only says that the boundary is at that index or to the left, so the search keeps going left to find the first one. That is how duplicates are handled: with [1, 2, 2, 2, 3] and value = 2, the search ends at index 1.

    Step by step

    1. Set up the window. Declare left and right in one :=: the first index and the last index, len(nums)-1.
    2. Loop while the window is non-empty, with a for that has only the condition left <= right. (Go has no while.)
    3. Compute middle. (left + right) / 2 rounds down, so it is always a valid index inside the window.
    4. Too small: if nums[middle] < value, the boundary is to the right, so set left = middle + 1.
    5. Big enough: otherwise nums[middle] is at least value, so the answer is middle or somewhere before it. Set right = middle - 1.
    6. Return left. When the loop ends, right is just one less than left. Everything before left is smaller than value, and everything from left on is at least value, so left is the boundary.

    The solution in Go

    func lowerBound(nums []int, value int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        middle := (left + right) / 2
        if nums[middle] < value {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return left
}

    Trace with nums = [1, 2, 3, 5, 7] and value = 4. First left = 0, right = 4, middle = 2, and nums[2] = 3 is smaller than 4, so left = 3. Next middle = 3 and nums[3] = 5 is not smaller, so right = 2. Now left > right, and the function returns 3.

    Go details in this code

    • Integer division. (left + right) / 2 is integer division because both operands are int; it truncates. Both indices are never negative inside the loop, so truncation is the same as rounding down.
    • The sum doesn't overflow. Go's int is 64 bits on 64-bit platforms, and slice indices are far below that. The variant left + (right-left)/2 is a good habit for languages with 32-bit integers, but it isn't needed here.
    • The result can be len(nums). When every element is smaller than value, left ends one past the last index. That is correct as an insert position, but it is not a valid index to read, so never write nums[lowerBound(...)] without checking.
    • A short condition-only for. for left <= right { ... } is Go's replacement for while.

    Complexity

    Time: O(log n). Each iteration discards at least half of the window, so the loop runs about log₂(n) times.

    Space: O(1). Only left, right and middle are stored.

    Edge cases and common mistakes

    • Empty slice. right is -1, the loop doesn't run, and the function returns 0.
    • Value smaller than everything. For [1, 2, 3] and value = 0, right keeps moving left until it reaches -1, and left stays 0. The answer is 0.
    • Value larger than everything. For [1, 2, 3] and value = 9, the answer is 3, the length of the slice.
    • Duplicates. The answer is the first of the equal elements. Returning as soon as nums[middle] == value would give any of them, which is wrong here.
    • Using <= in the comparison. With nums[middle] <= value the search moves past equal elements and finds the position after the last one, a different function (the upper bound).
    • Returning right. After the loop right is one before the boundary, so returning it is off by one.

    Testing

    • [1, 2, 3, 5, 7], 4 gives 3.
    • [1, 2, 3], 2 gives 1.
    • [1, 2, 2, 2, 3], 2 gives 1.
    • [1, 2, 3], 9 gives 3.
    • [], 5 gives 0.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free