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

arr = [1, 2, 4, 4, 4, 7, 9]
target = 4
lo = 0
hi = len(arr) - 1
result = -1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        result = mid
        hi = mid - 1
    elif arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(result)

Complexity

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

Implementation notes

Python stores arr as a list of references to immutable int objects. The search only reads arr[mid]; it never mutates the list or allocates a replacement container.
lo, hi, mid, and result are local integer bindings. The midpoint uses lo + (hi - lo) // 2, and the while lo <= hi guard keeps every arr[mid] access inside the current bounds.
On equality, the code records result = mid and then sets hi = mid - 1 to keep searching left. GC is not part of the visible loop state; the trace shows result move from -1 to 3, then to the first occurrence at 2.

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

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