Searching

Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.
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, 2, 4, 4, 4, 7, 9];
$target = 4;
$lo = 0;
$hi = count($arr) - 1;
$result = -1;
while ($lo <= $hi) {
	$mid = intdiv($lo + $hi, 2);
	if ($arr[$mid] == $target) {
		$result = $mid;
		$hi = $mid - 1;
	} elseif ($arr[$mid] < $target) {
		$lo = $mid + 1;
	} else {
		$hi = $mid - 1;
	}
}
echo $result . "\n";

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1<?php2$arr = [1, 2, 4, 4, 4, 7, 9];
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    7while ($lo <= $hi) {8	$mid = intdiv($lo + $hi, 2);9	if ($arr[$mid] == $target) {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    7while ($lo <= $hi) {8	$mid = intdiv($lo + $hi, 2);9	if ($arr[$mid] == $target) {
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    7while ($lo <= $hi) {8	$mid = intdiv($lo + $hi, 2);9	if ($arr[$mid] == $target) {
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    17}18echo $result . "\n";
    values this step2stdout2result

Complexity

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

Implementation notes

  • The sorted PHP array literal is [1, 2, 4, 4, 4, 7, 9], and $target is 4.
  • $lo starts at 0, $hi starts at count($arr) - 1, and $result = -1 is the not-found sentinel until a match is recorded.
  • The loop guard is while ($lo <= $hi), so each pass keeps the active search window explicit.
  • $mid = intdiv($lo + $hi, 2) uses PHP integer division for the midpoint.
  • A match uses $arr[$mid] == $target, records $result = $mid, then sets $hi = $mid - 1 so the loop keeps looking for an earlier duplicate.
  • If $arr[$mid] < $target, $lo moves right; otherwise $hi moves left.
  • The trace starts with lo=0, hi=6, mid=3; value 4 matches, so result=3 and hi=2.
  • Next mid=1 reads value 2, so lo moves to 2 while result stays 3.
  • The final checked step has lo=2, hi=2, mid=2; value 4 matches, result becomes 2, and hi=1 ends the loop.
  • echo $result . "\n"; prints 2, the first index of 4 in the pinned data.