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

Basic Implementation

basic.rb

arr = [1, 3, 5, 7, 9, 11, 13]
target = 11
lo = 0
hi = arr.length - 1
result = -1
done = false
while !done && lo <= hi
	mid = lo + (hi - lo) / 2
	if arr[mid] == target
		result = mid
		done = true
	elsif arr[mid] < target
		lo = mid + 1
	else
		hi = mid - 1
	end
end
puts result

The pinned run searches for 11 in [1, 3, 5, 7, 9, 11, 13]. The diagrams highlight the inclusive [lo, hi] window and each midpoint.

Step 1 - First midpoint is too small

lo = 0, hi = 6, mid = 3, and arr[3] = 7 is below target 11.

Step 2 - Window narrows to the right

Because 7 < 11, set lo = 4 and keep hi = 6.

Step 3 - Second midpoint matches

Now mid = 5 and arr[5] = 11, so the algorithm returns index 5.

Complexity

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

Implementation notes

Ruby: compute mid = lo + (hi - lo) / 2, not (lo + hi) / 2. Ruby Integer is arbitrary-precision so overflow is not a worry, but keeping the lesson aligned with overflow-safe practice across languages keeps the invariant honest.
arr.bsearch { |x| target <=> x } would hide the window-halving loop; the lesson is teaching the loop directly. A small done = false flag plus !done && lo <= hi keeps the match-and-exit path visible without leaning on break.
The replay highlights the [lo, hi] window, marks mid, and labels the branch taken (left half / right half / match).

midpoint `mid = lo + (hi - lo) / 2` (overflow-safe integer division).

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