Searching

Binary Search (Recursive)

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

Algorithm

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.

Basic Implementation

basic.lua
Replay: real traced execution (multi-file project)
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))

  1. lo ← 0, hi ← 6, target ← 11

    1arr = {1, 3, 5, 7, 9, 11, 13}2target = 11
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    6end7mid = lo + math.floor((hi - lo) / 2)8value = arr[mid + 1]
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    6end7mid = lo + math.floor((hi - lo) / 2)8value = arr[mid + 1]
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    16end17print(search(0, #arr - 1))
    values this step5stdout5result

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.