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 Lua DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.lua
Replay: real traced execution (multi-file project)
arr = {1, 2, 4, 4, 4, 7, 9}
target = 4
lo = 0
hi = #arr - 1
result = -1
while lo <= hi do
	mid = lo + math.floor((hi - lo) / 2)
	value = arr[mid + 1]
	if value == target then
		result = mid
		hi = mid - 1
	elseif value < target then
		lo = mid + 1
	else
		hi = mid - 1
	end
end
print(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 <= hi do7	mid = lo + math.floor((hi - lo) / 2)8	value = arr[mid + 1]
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    6while lo <= hi do7	mid = lo + math.floor((hi - lo) / 2)8	value = arr[mid + 1]
    values this step0 → 2lo1mid2hi3result

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

    6while lo <= hi do7	mid = lo + math.floor((hi - lo) / 2)8	value = arr[mid + 1]
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    17end18print(result)
    values this step2stdout2result

Complexity

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

Implementation notes

  • arr = {1, 2, 4, 4, 4, 7, 9} is a Lua table, and target = 4.
  • The search window uses zero-based logical indexes: lo = 0 and hi = #arr - 1, so the trace starts at 0..6.
  • Lua table access is still 1-based, so the probed value is read with value = arr[mid + 1].
  • mid = lo + math.floor((hi - lo) / 2) computes the middle without leaving fractional values.
  • result = -1 is the not-found sentinel until a match is recorded.
  • On value == target, the code sets result = mid and then moves hi = mid - 1 to keep searching for an earlier duplicate.
  • If value < target, lo moves right with lo = mid + 1; otherwise hi moves left.
  • The trace probes mid=3, matches 4, records result=3, and narrows left to hi=2.
  • It then probes mid=1, reads value 2, moves lo to 2, and finally probes mid=2, recording the first occurrence.
  • print(result) outputs 2, the zero-based index of the first 4.