$ceiling) { return -1; } // search the left part of the $array // If the $middle element is greater than the $value if ($arr[$mid] > $value) { return binarySearch($arr, $value, $floor, $mid - 1); } else { // search the right part of the $array If the $middle element is lower than the $value return binarySearch($arr, $value, $mid + 1, $ceiling); } } /** * @param Array $arr * @param int $value * @return int */ function exponentialSearch($arr, $value) { // If $value is the first element of the $array return this position if ($arr[0] === $value) { return 0; } // Find range for binary search $i = 1; $length = count($arr); while ($i < $length && $arr[$i] <= $value) { $i = $i * 2; } $floor = $i / 2; $ceiling = min($i, $length); // Call binary search for the range found above return binarySearch($arr, $value, $floor, $ceiling); }