Searching

Binary Search First Occurrence

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

Algorithm

Basic Implementation

basic.php 
<?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";

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