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

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.

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.