Binary Search for First and Last Occurrence

1. The Brute-Force Approach: Linear Scan

Following our established method, let's start with the most straightforward approach. Given the task of finding the first and last occurrence, the simplest idea is to just walk through the array.

We can use a single loop to iterate from the beginning to the end of the array. We would maintain two variables, say first and last, both initialized to -1.

• The very first time we encounter the target element, we set first to the current index.
• Every time we see the target element, we update last with the current index.

After the loop completes, first will hold the index of the first occurrence, and last will hold the index of the last one.

This approach is correct, but its time complexity is $O(n)$. The moment you hear "sorted array" and "search", you should immediately think of binary search. An $O(n)$ solution for a sorted array search problem is almost always a signal that a more optimal, logarithmic solution exists.

2. Optimal Approach 1: Leveraging lower_bound and upper_bound

This is where our work from the previous lesson pays off. Let's recall the definitions:

• lower_bound(x): Returns the index of the first element that is greater than or equal to x.
• upper_bound(x): Returns the index of the first element that is strictly greater than x.

How can we use these to find the first and last occurrences of our target x?

• First Occurrence: The definition of lower_bound(x) is exactly what we need for the first occurrence. It gives us the index of the first element that is >= x. If this element is indeed x, we've found our first occurrence.
• Last Occurrence: This is a bit more clever. upper_bound(x) gives us the index of the first element that is > x. The element just before this must therefore be the last element that is <= x. So, the index of the last occurrence of x is simply upper_bound(x) - 1.

This gives us a very elegant two-step solution:

1. Calculate first = lower_bound(x).
2. Calculate last = upper_bound(x) - 1.

Of course, we must handle the edge case where the element x is not in the array. We can do this by checking the result of our lower_bound call. If the index it returns is out of bounds, or if the element at that index is not our target x, then the element does not exist in the array, and we should return [-1, -1].

This approach is highly efficient, with a time complexity of $O(\log n)$ because it just involves two binary search operations. It's a powerful demonstration of how reusing well-understood patterns (lower_bound, upper_bound) can lead to clean and optimal solutions.

Here's how this would look in Java, using the lowerBound and upperBound functions we developed in the previous lesson:

public int[] searchRange(int[] nums, int target) {
    int lb = lowerBound(nums, target);

    // Check if the target exists
    if (lb == nums.length || nums[lb] != target) {
        return new int[]{-1, -1};
    }

    int ub = upperBound(nums, target);
    return new int[]{lb, ub - 1};
}

3. Optimal Approach 2: Two Modified Binary Searches

While the lower_bound/upper_bound method is elegant, some interviewers might ask you to implement the logic from scratch without relying on helper functions. This requires modifying the standard binary search algorithm. We'll need to run it twice: once to find the first position, and once to find the last.

Finding the First Occurrence

The goal is to find the leftmost index of the target.

1. Perform a standard binary search.
2. If arr[mid] == target, we have found a potential answer. We store this index, say in a variable first = mid. However, there might be another occurrence of the target to the left. So, we don't stop. We continue searching in the left half by setting high = mid - 1.
3. If arr[mid] < target, we search the right half (low = mid + 1).
4. If arr[mid] > target, we search the left half (high = mid - 1).

By repeatedly trying to search leftward after finding a match, we ensure that our first variable will eventually hold the index of the leftmost occurrence.

Finding the Last Occurrence

The logic is symmetric. The goal is to find the rightmost index.

1. Perform another binary search.
2. If arr[mid] == target, we have found a potential answer. We store this index, say in last = mid. But there might be more occurrences to the right. So, we continue searching in the right half by setting low = mid + 1.
3. The rest of the binary search logic remains the same.

This ensures our last variable will hold the index of the rightmost occurrence.

The following video provides a fantastic, step-by-step walkthrough of this two-pass binary search approach in Java.

For a full implementation in Java, you can study the following article from takeuforward. It presents the complete code with helper functions for firstOccurrence and lastOccurrence.

4. Application: Counting Occurrences

A very common follow-up question is: "Now, can you count the total number of times the target appears in the array?"

Once you have the first and last occurrences, this becomes trivial. If first is the index of the first occurrence and last is the index of the last one, the total count is simply:

$\text{count}=\text{last}-\text{first}+1$

If the element was not found (first == -1), the count is 0. This simple formula is the reason why finding the first and last positions is such a foundational problem.

Conclusion

Today, we've dissected a cornerstone binary search problem. We explored three distinct paths to the solution: a simple but inefficient linear scan, an elegant and optimal solution using lower_bound and upper_bound, and a fundamental implementation using two modified binary searches. For interviews, it's crucial to understand both optimal approaches.

Key Takeaways:

• Problem: Find the start and end index of a target in a sorted array with duplicates.
• Brute-Force: An $O(n)$ linear scan can find the first and last indices but is inefficient.
• Optimal Approach 1 (Pattern-based): Use lower_bound to find the first occurrence and upper_bound - 1 to find the last. This is an $O(\log n)$ solution that relies on pre-existing patterns.
• Optimal Approach 2 (Implementation-based): Run two modified binary searches. The first search continues leftward on a match to find the first occurrence. The second search continues rightward on a match to find the last. This is also an $O(\log n)$ solution.
• Application: The number of occurrences can be calculated as last_index - first_index + 1.

In our next lesson, we'll continue to stretch our binary search skills by tackling another classic variation: searching in a rotated sorted array. This will challenge us to find a way to apply binary search even when the array isn't perfectly sorted from end to end.