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

Finding First Occurrence

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

Finding First Occurrence

What You'll Learn

You'll learn how to modify binary search to find the leftmost (first) occurrence of a target value when duplicates exist in a sorted array.

The Problem with Standard Binary Search

Standard binary search finds a match, but when duplicates exist, you don't know if it's the first one. For example, in [1, 2, 4, 4, 4, 7, 9], searching for 4 might return index 2, 3, or 4—whichever the algorithm happens to land on first.

The Core Modification

To guarantee finding the first occurrence, we adjust the strategy:

  1. When we find a match, don't return immediately
  2. Instead, record that position as a potential answer
  3. Continue searching left (in the lower half) to see if an earlier occurrence exists
  4. Only stop when the search range is exhausted

Think of it like looking for the first page where a word appears in a dictionary. Even when you find it, you flip backward to make sure there isn't an earlier page with that same word.

The Algorithm

When arr[mid] == target:

  • Save mid as a candidate result
  • Set right = mid - 1 (search the left half)
  • Continue the loop

When arr[mid] < target:

  • Set left = mid + 1 (target must be to the right)

When arr[mid] > target:

  • Set right = mid - 1 (target must be to the left)

The key difference from standard binary search: we don't stop at the first match—we keep narrowing left until we've confirmed no earlier occurrence exists.

Time Complexity

Still O(log n)—we're just being pickier about which match we accept.

Key Takeaway: To find the first occurrence in a sorted array with duplicates, continue searching left even after finding a match, treating each match as a "best so far" candidate until the search space is exhausted.