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

object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(1, 3, 5, 7, 9, 11, 13)
		val target = 11
		var lo = 0
		var hi = arr.length - 1
		var result = -1
		var done = false
		while (!done && lo <= hi) {
			val mid = lo + (hi - lo) / 2
			if (arr(mid) == target) {
				result = mid
				done = true
			} else if (arr(mid) < target) {
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
		println(result)
	}
}

Complexity

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

Implementation notes

Scala: compute val mid = lo + (hi - lo) / 2, not (lo + hi) / 2. Keeps the lesson aligned with overflow-safe practice even on small inputs.
java.util.Arrays.binarySearch(arr, target) would hide the window-halving loop; the lesson is teaching the loop directly. A small var done = false flag plus !done && lo <= hi keeps the match-and-exit path visible without leaning on scala.util.boundary.
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`.