Searching

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

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";

The pinned run searches for 11 in [1, 3, 5, 7, 9, 11, 13]. The diagrams highlight the inclusive [lo, hi] window and each midpoint.

Step 1 - First midpoint is too small

lo = 0, hi = 6, mid = 3, and arr[3] = 7 is below target 11.

Probe 1 keeps the right half.i0i1i2i3i4i5i6135791113lomidtargethi

Step 2 - Window narrows to the right

Because 7 < 11, set lo = 4 and keep hi = 6.

After discarding indexes 0 through 3.i0i1i2i3i4i5i6135791113discarddiscarddiscarddiscardlomidhi

Step 3 - Second midpoint matches

Now mid = 5 and arr[5] = 11, so the algorithm returns index 5.

Probe 2 finds target 11 at index 5.i4i5i6return911135lomid == targethiindex

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