Exponential Search

exponentialSearch.php

<?php

function binarySearchRecursion($array, $find, $left, $right)  
{  
    if ($left > $right) {  
        return -1;  
    }  
  
    $middle = floor( ($left + $right) / 2 );
  
    if ($find === $array[$middle]) {  
        return $middle;  
    } elseif ($find < $array[$middle]) {  
        return binarySearchRecursion($array, $find, $left, $middle-1);  
    }     
  
    return binarySearchRecursion($array, $find, $middle+1, $right); // our key might be in the right sub-array  
}   

function exponentialSearch($array, $find)
{
    $size = count($array);

    if ($size == 0) {
        return -1;
    }

    $bound = 1;
    while ($bound < $size && $array[$bound] < $find) {	
        $bound *= 2;
    }

    return binarySearchRecursion($array, $find, $bound/2, min($bound, $size));
}

$array = [2,4,5,7,8,13,14,15,26,27,29,31,44,45,46,66,67,68,69,71,80];
$find = 71;

$result = exponentialSearch($array, $find);
echo "Found $find at index $result";
?>