Searching

Binary Search First Occurrence

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

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.
cross-language comparison This Ruby DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.rb
Replay: real traced execution (multi-file project)
arr = [1, 2, 4, 4, 4, 7, 9]
target = 4
lo = 0
hi = arr.length - 1
result = -1
while lo <= hi
	mid = lo + (hi - lo) / 2
	if arr[mid] == target
		result = mid
		hi = mid - 1
	elsif arr[mid] < target
		lo = mid + 1
	else
		hi = mid - 1
	end
end
puts result

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1arr = [1, 2, 4, 4, 4, 7, 9]2target = 4
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    6while lo <= hi7	mid = lo + (hi - lo) / 28	if arr[mid] == target
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    6while lo <= hi7	mid = lo + (hi - lo) / 28	if arr[mid] == target
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    6while lo <= hi7	mid = lo + (hi - lo) / 28	if arr[mid] == target
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    1arr = [1, 2, 4, 4, 4, 7, 9]2target = 4
    values this step2stdout2result

Complexity

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

Implementation notes

  • arr is a Ruby Array read by index; the search never mutates it.
  • lo, hi, mid, and result are local integer variables reassigned during the while lo <= hi loop.
  • The midpoint uses mid = lo + (hi - lo) / 2; Ruby integer division keeps mid as an integer index.
  • result starts at -1, so a miss would keep the sentinel value.
  • On arr[mid] == target, the code records result = mid and then sets hi = mid - 1 to keep searching for an earlier copy.
  • If arr[mid] < target, lo = mid + 1; otherwise hi = mid - 1.
  • The trace first matches at index 3, moves left, skips value 2 at index 1, then matches index 2 as the first occurrence.
  • puts result prints the final scalar index 2.