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

package main

import "fmt"

func main() {
	arr := []int{1, 3, 5, 7, 9, 11, 13}
	target := 11
	lo := 0
	hi := len(arr) - 1
	result := -1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if arr[mid] == target {
			result = mid
			break
		}
		if arr[mid] < target {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	fmt.Println(result)
}

Complexity

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

Implementation notes

Go: compute mid := lo + (hi-lo)/2, not (lo+hi)/2. Keeps the lesson aligned with overflow-safe practice even on small inputs.
Go's sort.Search would hide the window-halving loop; the lesson is teaching the loop directly.
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`.