PHP 7 Data Structures and Algorithms

Exponential search

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); ...