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

let arr = [1, 3, 5, 7, 9, 11, 13]
let target = 11
var lo = 0
var hi = arr.count - 1
var result = -1
while lo <= hi {
	let mid = lo + (hi - lo) / 2
	if arr[mid] == target {
		result = mid
		break
	}
	if arr[mid] < target {
		lo = mid + 1
	} else {
		hi = mid - 1
	}
}
print(result)

Complexity

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

Implementation notes

Swift: compute let mid = lo + (hi - lo) / 2, not (lo + hi) / 2. Keeps the lesson aligned with overflow-safe practice even on small inputs.
The stdlib does not ship a generic binary search, so the lesson can stay on the explicit window-halving loop. lo and hi are kept as Int so the -1 initialisation of result is honest without Int?.
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`.