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.c

#include <stdio.h>

int main(void) {
    int arr[] = {1, 2, 4, 4, 4, 7, 9};
    int n = (int)(sizeof(arr) / sizeof(arr[0]));
    int target = 4;
    int lo = 0;
    int hi = n - 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;
        }
    }
    printf("%d\n", result);
    return 0;
}

Complexity

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

Implementation notes

C stores the sorted input as a fixed local int arr[] = {1, 2, 4, 4, 4, 7, 9} and computes n with (int)(sizeof(arr) / sizeof(arr[0])) before any pointer decay.
The search state is all scalar stack data in main: lo = 0, hi = n - 1, target = 4, and result = -1 as the not-found sentinel.
mid uses signed arithmetic, lo + (hi - lo) / 2, and arr[mid] is read by index inside while (lo <= hi).
On a match, the code mutates result = mid and then narrows left with hi = mid - 1, so later matches can replace the recorded index with an earlier one.
The trace records mid=3 setting result=3 and hi=2, mid=1 moving lo=2, then mid=2 setting result=2 and hi=1 before exit.
printf("%d\n", result) prints 2. Visible memory is the stack array plus scalar locals; there is no helper function taking an array pointer in this source.

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.