Searching

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

  • In C++, the input is a std::vector<int> initialized as {1, 2, 4, 4, 4, 7, 9} and read by index; the vector is never mutated.
  • Search bounds are scalar int values. hi starts at static_cast<int>(arr.size()) - 1, and the loop continues while lo <= hi.
  • The midpoint uses lo + (hi - lo) / 2, avoiding the direct lo + hi addition while still producing an int index for arr[mid].
  • int result = -1 is the not-found sentinel. On a match, the code records result = mid and sets hi = mid - 1 so duplicate targets keep searching left.
  • The trace records mid=3 with result=3, then mid=1 moving lo to 2, then mid=2 updating the first occurrence to result=2.
  • std::cout << result << "\n" writes 2. Visible allocation is the vector storage from the initializer list; mutation is limited to scalar search state.
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.