Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

Basic Implementation

basic.lua

arr = {1, 3, 5, 7, 9, 11, 13}
target = 11
function search(lo, hi)
	if lo > hi then
		return -1
	end
	mid = lo + math.floor((hi - lo) / 2)
	value = arr[mid + 1]
	if value == target then
		return mid
	end
	if value < target then
		return search(mid + 1, hi)
	end
	return search(lo, mid - 1)
end
print(search(0, #arr - 1))

Complexity

Time: O(log n)
Space: O(log n) call stack

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-recursive`.

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