Searching

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

  • arr = {1, 3, 5, 7, 9, 11, 13} is the Lua table being searched, and target = 11.
  • function search(lo, hi) closes over arr and target; only the logical zero-based bounds are passed through recursive calls.
  • The initial call is search(0, #arr - 1), so the trace starts with lo=0, hi=6.
  • The base case is if lo > hi then return -1 end.
  • mid = lo + math.floor((hi - lo) / 2) keeps midpoint arithmetic integral.
  • Lua table access is 1-based, so the probed value is read with value = arr[mid + 1].
  • If value == target, the function returns mid, a zero-based index.
  • If value < target, the recursive call is search(mid + 1, hi); otherwise it is search(lo, mid - 1).
  • The trace probes mid=3, reads value 7, and recurses right to (4, 6).
  • The next call probes mid=5, reads 11, returns 5, and print(...) outputs 5.
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.