Searching

Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.
cross-language comparison This PHP DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.php
Replay: real traced execution (multi-file project)
<?php
$arr = [1, 3, 5, 7, 9, 11, 13];
$target = 11;
function search($arr, $target, $lo, $hi) {
	if ($lo > $hi) {
		return -1;
	}
	$mid = intdiv($lo + $hi, 2);
	if ($arr[$mid] == $target) {
		return $mid;
	}
	if ($arr[$mid] < $target) {
		return search($arr, $target, $mid + 1, $hi);
	}
	return search($arr, $target, $lo, $mid - 1);
}
echo search($arr, $target, 0, count($arr) - 1) . "\n";

  1. lo ← 0, hi ← 6, target ← 11

    1<?php2$arr = [1, 3, 5, 7, 9, 11, 13];
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    7}8$mid = intdiv($lo + $hi, 2);9if ($arr[$mid] == $target) {
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    7}8$mid = intdiv($lo + $hi, 2);9if ($arr[$mid] == $target) {
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    16}17echo search($arr, $target, 0, count($arr) - 1) . "\n";
    values this step5stdout5result

Complexity

  • Time: O(log n)
  • Space: O(log n) call stack

Implementation notes

  • The sorted PHP array literal is [1, 3, 5, 7, 9, 11, 13], and $target is 11.
  • search($arr, $target, $lo, $hi) carries the current window through function parameters instead of mutating outer loop variables.
  • The initial call is search($arr, $target, 0, count($arr) - 1), so the first replayed window is lo=0, hi=6.
  • The base case is if ($lo > $hi) return -1;, which is the only not-found exit in this source.
  • $mid = intdiv($lo + $hi, 2) uses PHP integer division to choose the center index.
  • The first trace step reads mid=3, arr[mid]=7; because 7 < 11, the code recurses right with search($arr, $target, $mid + 1, $hi), narrowing to (4, 6).
  • In the second window, mid=5 and arr[mid]=11, so the function returns 5 directly.
  • The left-branch call search($arr, $target, $lo, $mid - 1) is present in the code but is not taken by this pinned trace.
  • echo search(...) . "\n"; prints 5, the index of 11 in the checked data.