Course contentsShow
← Computer Science
Lesson 813 of 2,87219. Searching and SelectionFree lesson

Finding Last Occurrence

Modify binary search to locate the rightmost occurrence of a target value in a sorted array with duplicates.

Finding Last Occurrence

You'll learn how to modify binary search to find the rightmost position of a target value in a sorted array that contains duplicates.

When you have a sorted array with repeated elements like [1, 2, 3, 3, 3, 5, 7] and search for 3, standard binary search might land anywhere among the three occurrences. But what if you specifically need the last (rightmost) occurrence—the one at index 4?

The Core Idea

Finding the last occurrence is the mirror image of finding the first occurrence. Instead of moving left when you find a match (to check if there's an earlier one), you move right to check if there's a later one.

The algorithm works like this:

  1. Perform binary search as usual
  2. When you find the target value, don't stop—save that index as a candidate
  3. Continue searching in the right half (indices greater than mid)
  4. Keep updating your candidate whenever you find the target
  5. When the search space is exhausted, return your last-saved candidate

Think of it like looking for the last person named "Smith" in an alphabetically sorted phone book. When you find a Smith, you keep flipping pages forward until you're sure there are no more Smiths after them.

Why This Works

By persistently searching to the right of each match, you ensure that when no more matches exist to the right, you've found the rightmost occurrence. The binary search structure guarantees you check this efficiently in O(log n) time.

Key Takeaway: To find the last occurrence in a sorted array with duplicates, modify binary search to continue searching the right half even after finding a match, tracking the rightmost position seen until the search space is empty.