Binary Search (Iterative)

On a sorted array, narrow [lo, hi] window by halving until arr[mid] equals the target or the window is empty. Demonstrates the "discard half the search space" invariant.

Algorithm

Canonical input arr = {1, 3, 5, 7, 9, 11, 13} with target = 11 finishes in two frames: descend right to mid = 6, match.

Basic Implementation

basic.lua

local arr = {1, 3, 5, 7, 9, 11, 13}
local target = 11
local lo = 1
local hi = #arr
local result = -1
local done = false
while not done and lo <= hi do
	local mid = lo + (hi - lo) // 2
	if arr[mid] == target then
		result = mid
		done = true
	elseif arr[mid] < target then
		lo = mid + 1
	else
		hi = mid - 1
	end
end
print(result)

Complexity

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

Implementation notes

Lua 5.3+ ships a floor-divide operator //, so mid = lo + (hi - lo) // 2 returns an integer directly without the pre-5.3 math.floor((lo + hi) / 2) workaround.
A small done = false flag plus not done and lo <= hi keeps the match-and-exit path visible without leaning on a break jump.
The replay highlights the [lo, hi] window, marks mid, and labels the branch taken (left half / right half / match). The 1-based index means the match position prints as 6 instead of 5 like the 0-indexed language cohorts.

midpoint `mid = lo + (hi - lo) // 2` (overflow-safe integer division using Lua 5.3+ floor-divide).

inclusive window `hi` is inclusive. The loop runs while `lo <= hi`.