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

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)

Complexity

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

Implementation notes

Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
The final output is intentionally small and deterministic for cross-language comparison.

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.