Searching

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 = 5, match.

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

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