Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

Basic Implementation

basic.cpp

#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<int> arr{1, 2, 4, 4, 4, 7, 9};
    int target = 4;
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;
    int result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            result = mid;
            hi = mid - 1;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    std::cout << result << "\n";
    return 0;
}

Complexity

Time: O(log n)
Space: O(1)

Implementation notes

Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
The final output is intentionally small and deterministic for cross-language comparison.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.

cross-language comparison This C++ DSA version keeps the same data and final output as every other DSA book in this wave.