In binary search, we are searching the whole list for a given key. Exponential search improves binary search by deciding the lower and upper bound of the search so that we do not end up searching the whole list. It improves the number of comparisons we need to find an element. The search is done in the following two steps:

1. We determine the bound size by looking for the first exponent k where the value of 2^k is greater than the search item. Now, 2^k and 2^k-1 become the upper bound and lower bound, respectively.
2. Apply binary search algorithm for the bound 2^k and 2^k-1.

Let's now implement the exponential search using our recursive binarySearch function:

function exponentialSearch(array $arr, int $key): int { 
    $size = count($arr); 

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

    $bound = 1; 
    while ($bound < $size && $arr[$bound] < $key) { 
      $bound *= 2; 
    } 
    return binarySearch($arr, $key, intval($bound / 2),  
min($bound, $size)); 
}

Here, in step one, we are taking i steps to determine the boundary. So, the algorithm takes O(log i) complexity. We have to remember that here, i is much smaller than n. Then, we are doing a binary search with a bound of 2^j to 2^j-1where j = log i. We know binary search takes O(log n) complexity where n is the size of the list. However, since we are doing a smaller bound search, we are actually searching 2 ^{log i} - 2 ^{log i} - 1 = 2 ^{log i - 1} size. So, the complexity of this bound will be log (2 ^{log i - 1}) = log (i) - 1 = O(log i).

So, the complexity of the exponential search is as follows: