Binary Search: Split Happens

I didn’t get it right on the first try.

That’s okay.

What matters is understanding the idea.

What it is:

If a list is sorted, you don’t scan it from start to end. You jump to the middle, decide which half could contain the value, and throw the other half away.

Repeat until you find it (or the range is empty).

How it works :

Keep two pointers: left and right. Pick the middle index. If the middle value is your target — done. If it’s smaller — search the right half. If it’s bigger — search the left half. Stop when left goes past right.

Why it’s fast:

Each step throws away half of the list. That’s about log2(n) checks (e.g., ~20 checks for a million items), instead of up to a million.

PHP implementation:

$a = [-1,0,2,4,6,8,16,44,66,77,90,91,92,93,94,95,96,97,98,99]; //The array must be sorted.
$needle = 97;
function position($arr, $needle, $left = null, $right = null) {
 if ($left === null || $right === null) {
  $left = 0;
  $right = count($arr) - 1;
 }
 $mid = intdiv($left + $right, 2);
 if ($arr[$mid] === $needle) return $mid;
  if ($arr[$mid] < $needle){
   return position($arr, $needle, $mid + 1, $right);
  }
else {
 return position($arr, $needle, $left, $mid - 1);
 }
}
var_dump(position($a,$needle));