Binary Search for Insertion and Range Finding

1. The Lower Bound: Finding the Insertion Point

Our standard binary search stops as soon as it finds a match. But what if we need to find the first possible position for a target? This is useful for two scenarios:

1. Finding the index to insert a new element while maintaining sorted order.
2. Finding the starting index of a target that might have duplicates.

This position is formally known as the lower bound.

Lower Bound: The smallest index i in a sorted array such that nums[i] >= target.

To find the lower bound, we modify our binary search logic: even when we find an element nums[mid] that is >= target, we don't stop. We record this mid as a potential answer and then try to find an even smaller index to its left.

Let's watch a video that explains this concept and walks through the implementation logic.

Here is a Python implementation of the lower_bound function based on the logic from the video:

def lower_bound(nums, target):
    """
    Finds the first index i such that nums[i] >= target.
    Returns len(nums) if all elements are smaller than target.
    """
    left, right = 0, len(nums) - 1
    ans = len(nums)  # Default answer if no element is >= target

    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] >= target:
            # This is a potential answer. Store it and look for a better one (smaller index) to the left.
            ans = mid
            right = mid - 1
        else: # nums[mid] < target
            # The answer must be in the right half.
            left = mid + 1
            
    return ans

This exact logic solves the LeetCode problem "Search Insert Position" (LC 35). If the target is in the array, lower_bound will find its first occurrence. If it's not, it will find the index where it should be inserted. The video confirms this connection in the segment starting at 19:36.

2. Finding a Search Range: First and Last Position

A very common interview problem (LeetCode 34: Find First and Last Position of Element in Sorted Array) asks you to find the starting and ending index of a target value that may appear multiple times.

For example, in [5, 7, 7, 8, 8, 10], for target = 8, the answer is [3, 4].

We can solve this by performing two modified binary searches:

1. Find the first occurrence: This is simply the lower_bound of the target.
2. Find the last occurrence: We can do this by finding the lower_bound of target + 1 and subtracting 1 from the result. This clever trick finds the first element greater than our target, and the element right before it must be the last occurrence of our target.

This "upper bound" concept is the natural counterpart to the lower bound.

Upper Bound: The smallest index i in a sorted array such that nums[i] > target.

The implementation is nearly identical to lower_bound, with only a change from >= to >. The video you watched earlier also covers this.

Now we can combine these two functions to solve the search range problem.

def search_range(nums, target):
    # Find the first occurrence of the target
    start = lower_bound(nums, target)
    
    # If the start index is out of bounds or the element at start is not the target,
    # then the target is not in the array.
    if start == len(nums) or nums[start] != target:
        return [-1, -1]
        
    # Find the first occurrence of an element > target
    # This is the upper_bound of the target.
    # The last occurrence of the target will be the index right before it.
    end_index_exclusive = lower_bound(nums, target + 1)
    end = end_index_exclusive - 1
    
    return [start, end]

# lower_bound function as defined before
def lower_bound(nums, target):
    left, right = 0, len(nums) - 1
    ans = len(nums)
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

# Example:
nums = [5, 7, 7, 8, 8, 10]
target = 8
print(search_range(nums, target)) # Output: [3, 4]

target = 6
print(search_range(nums, target)) # Output: [-1, -1]

For a comprehensive text-based walkthrough of this problem, including the intuition, pitfalls, and code in multiple languages (Python, Java, C++), the following resource is excellent.

Conclusion

You have now extended your binary search skills beyond simple lookups. By making small but crucial modifications to the comparison logic, you can find boundaries and ranges efficiently.

Key Takeaways:

• Lower Bound: lower_bound(target) finds the first index i where nums[i] >= target. This is the key to solving "Search Insert Position".
• Upper Bound: upper_bound(target) finds the first index i where nums[i] > target.
• Search Range Strategy: The range of a target can be found by [lower_bound(target), upper_bound(target) - 1], after checking that the target exists.
• The Pattern: The core pattern is to not stop on a match, but to record it as a potential answer and continue shrinking the search space to find an even better (leftmost or rightmost) solution.

In our next lesson, we will push this pattern further by applying binary search to a more complex data structure: a rotated sorted array. This will challenge you to adapt the boundary conditions in a new way.