Skip to content

Instantly share code, notes, and snippets.

@andrewwoods
Created May 11, 2021 22:34
Show Gist options
  • Save andrewwoods/bc64d0989d3d28c1727957b283579b7b to your computer and use it in GitHub Desktop.
Save andrewwoods/bc64d0989d3d28c1727957b283579b7b to your computer and use it in GitHub Desktop.
Binary Search in PHP using recursion
#!/usr/bin/php
<?php
/*
* Binary Search Function - uses recursion
*
*/
function binarySearch(array $search, int $find): bool
{
$length = count($search);
// base condition. make it stop if necessary.
if ($length === 0) {
return false;
}
$mid_index = floor($length / 2);
$mid_value = $search[$mid_index];
if ($find === $mid_value) {
echo "FOUND IT! mid_value={$mid_value}\n";
return true;
}
// Default to the lower half
$low = 0;
$high = $mid_index;
if ($find > $mid_value) {
// Just kidding! it's in the upper half
$low = $mid_index + 1;
$high = $length;
}
$sub_length = $high - $low;
$new_search = array_slice($search, $low, $sub_length);
return binarySearch($new_search, $find);
}
// ------------------------------------------
// Test code
// ------------------------------------------
$search = [0, 1, 3, 5, 6, 7, 12, 23, 34, 88, 92, 96, 100];
$result = binarySearch($search, 3) ? "Found" : "Not Found";
echo "
-----------------------------
Result: $result
-----------------------------
\n";
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment