Binary Search (Iterative)

On a sorted vector, 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 <- c(1, 3, 5, 7, 9, 11, 13) with target <- 11 finishes in two frames: descend right to mid = 6, match.

Basic Implementation

basic.R

arr <- c(1, 3, 5, 7, 9, 11, 13)
target <- 11
lo <- 1
hi <- length(arr)
result <- -1
done <- FALSE
while (!done && lo <= hi) {
	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
	}
}
cat(result, "\n", sep = "")

Complexity

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

Implementation notes

R's %/% operator is floor-divide, so mid <- lo + (hi - lo) %/% 2 returns an integer directly without having to wrap as.integer(floor((lo + hi) / 2)).
A small done <- FALSE flag plus !done && lo <= hi keeps the match-and-exit path visible without leaning on a break jump.
The replay highlights the [lo, hi] window, marks mid, and labels the branch taken (left half / right half / match). The 1-based index means the match position prints as 6 instead of 5 like the 0-indexed language cohorts.

midpoint `mid <- lo + (hi - lo) %/% 2` (overflow-safe integer division using R's `%/%` floor-divide operator).

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