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

<?php
$arr = [1, 3, 5, 7, 9, 11, 13];
$target = 11;
$lo = 0;
$hi = count($arr) - 1;
$result = -1;
$done = false;
while (!$done && $lo <= $hi) {
	$mid = $lo + intdiv($hi - $lo, 2);
	if ($arr[$mid] == $target) {
		$result = $mid;
		$done = true;
	} else if ($arr[$mid] < $target) {
		$lo = $mid + 1;
	} else {
		$hi = $mid - 1;
	}
}
echo $result . "\n";

Complexity

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

Implementation notes

PHP: compute $mid = $lo + intdiv($hi - $lo, 2); rather than (int)(($lo + $hi) / 2). intdiv returns an int directly and keeps the lesson aligned with overflow-safe practice even on small inputs.
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).

midpoint `$mid = $lo + intdiv($hi - $lo, 2);` (overflow-safe integer division).

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