Binary Search First Occurrence Explained: Finding 3 in [1,3,3,3,5]

Imagine you are handed a sorted list of numbers containing duplicates: [1, 3, 3, 3, 5], and your mission is to find the first occurrence of the number 3. If you reach for a standard binary search, you calculate a midpoint, check if it equals 3, and happily return its index. But standard binary search has no loyalty to boundaries; it might land on index 2 or index 3 and stop immediately, completely oblivious to whether an earlier 3 is hiding to the left.

Now consider a second scenario: what if the target is 2, which does not even exist in our sorted list [1, 3, 5]? A standard binary search will eventually report failure (-1 or not found). Yet, in many practical systems—like database indexing or language runtimes—we do not just want to know if 2 is present. We need its exact insert position, the index where 2 belongs to keep the sequence sorted. Without a specialized approach, you are forced to scan the array linearly, throwing away the $O(\log n)$ speed advantage you bought by keeping the data sorted in the first place.

Standard binary search stops as soon as it hits any matching value. When our sorted nums is $[1,3,3,3,5]$ and target is 3, a naive search might land on index 2 and declare success. But our goal for a lower bound is much stricter: we want the first occurrence at index 1, or for the missing target 2 in $[1,3,5]$, the exact insertion index 1 where 2 belongs without breaking order.

To achieve this, we redefine our search space boundaries. Instead of setting hi = n - 1, we maintain our high pointer at hi = n. This allows our pointer to validly point to the index after the last element, which is essential if our target is larger than all elements in the array. Our search window is always a half-open range $[\text{lo},\text{hi})$.

When we compute $\text{mid}=(\text{lo}+\text{hi})//2$, we compare $\text{nums}[\text{mid}]$ against our target. If $\text{nums}[\text{mid}]<\text{target}$, we know $\text{mid}$ and everything to its left is strictly too small. We safely advance $\text{lo}=\text{mid}+1$. However, if $\text{nums}[\text{mid}]\ge \text{target}$, $\text{mid}$ itself could be our answer or our first occurrence might still lie further to the left. Therefore, we do not step past $\text{mid}$; instead, we pull our upper bound down by setting $\text{hi}=\text{mid}$.

Try this: Given nums = [1, 3, 5] and target = 2, what are the initial values of lo, hi, and mid on the very first iteration using this lower bound model?

To see how the lower bound invariant operates in practice, let us trace our locked example step by step. We have a sorted array nums = [1, 3, 3, 3, 5] and a target of 3. We want to locate its first occurrence. We initialize our search pointers across the full valid index range: lo = 0, hi = 5 (where $n=5$).

Given: nums = [1, 3, 3, 3, 5], target = 3
Steps:
- Iteration 1: lo = 0, hi = 5. Compute mid = (0 + 5) // 2 = 2. Inspect nums[2], which is 3. Since nums[2] >= target ($3ge3$), we must look to the left to see if an earlier 3 exists. We set hi = mid ($5\to 2$).
- Iteration 2: lo = 0, hi = 2. Compute mid = (0 + 2) // 2 = 1. Inspect nums[1], which is 3. Again, nums[1] >= target, so we set hi = mid ($2\to 1$).
- Iteration 3: lo = 0, hi = 1. Compute mid = (0 + 1) // 2 = 0. Inspect nums[0], which is 1. Since 1 < 3, nums[0] is too small. We advance the lower bound: lo = mid + 1 ($0\to 1$).
- Termination: Now lo = 1 and hi = 1. The loop condition lo < hi fails ($1<1$ is false). We terminate and return lo.

Result: Index 1, which is the exact first position of 3.

Now let us trace the second part of our working example: finding the insert position of target = 2 in nums = [1, 3, 5].
Given: nums = [1, 3, 5], target = 2, lo = 0, hi = 3 ($n=3$)
Steps:
- Iteration 1: lo = 0, hi = 3. Compute mid = (0 + 3) // 2 = 1. Inspect nums[1], which is 3. Since 3 >= 2, we set hi = 1.
- Iteration 2: lo = 0, hi = 1. Compute mid = (0 + 1) // 2 = 0. Inspect nums[0], which is 1. Since 1 < 2, we set lo = mid + 1 ($0\to 1$).
- Termination: lo = 1 and hi = 1. Loop terminates.

Result: Index 1, which correctly represents the insertion index where 2 belongs between 1 and 3 to keep the array sorted.

Now that you have traced how the invariant shrinks the window for both the first occurrence of 3 in [1, 3, 3, 3, 5] and the missing insertion point of 2 in [1, 3, 5], it is time to test your mental model on a boundary modification of the same data. Recall that the lower bound routine returns the first index $i$ where $\text{nums}[i]\ge \text{target}$, or $n$ if no such element exists.

Consider the original array [1, 3, 3, 3, 5] from our locked example, but change the target value to 0. Your task is to trace or mentally execute the lo and hi pointer updates to determine what index the algorithm will return and why the invariant prevents the pointers from breaking.

nums = [1, 3, 3, 3, 5]
target = 0
# What does binary_search_lower_bound(nums, target) return?

Now that you have traced the lower bound logic for [1, 3, 3, 3, 5] and handled the missing element 2 in [1, 3, 5], it is time to deploy this exact structural invariant to a new situation. Many problems that appear distinct—such as finding the frequency of a repeated element or locating the first bad version in a sequence of software builds—are actually direct disguises of the lower bound pattern.

For instance, suppose you need to count how many times the value 3 appears in the locked array [1, 3, 3, 3, 5]. Instead of scanning linearly, you can combine two binary searches: find the lower bound of 3 to lock down the starting index, and find the lower bound of $3+1$ (or an upper bound) to find the cutoff index. The difference between these two pointers yields the exact count in $O(\log n)$ time.

The core transfer skill is recognizing when a problem asks for a boundary transition from false to true (or less-than to greater-than-or-equal). Whenever you spot a sorted domain where you need the first transition point rather than any arbitrary match, throw away standard equality checking and instantiate the range $[0,n]$ with hi = n and else hi = mid.

Consider a sorted array of timestamps representing successful and failed system checks, where [0, 0, 0, 1, 1] denotes 0 for pass and 1 for fail. You need to find the exact index of the first system failure (1). State how you would adapt the lower bound template variables (target = 1, comparison operator, and pointer updates) to solve this without modifying the core invariant.

def find_first_failure(checks):
    lo, hi = 0, len(checks)
    while lo < hi:
        mid = (lo + hi) // 2
        # Adapt the condition below:
        if checks[mid] < 1:
            lo = mid + 1
        else:
            hi = mid
    return lo