Trouble in understanding how Exponential Search works

Question

I learn for my exam and learning search algorithms at the moment. I understood linear, binary and interpolation search and now try to understand exponential search. But there is bad source on the internet and if there is explanation is very complicated for me.. I hope you can clarify the algorithm?

Edit (tryd to correct my mistake):

So let's say we have array and we search for 19 in the array:

Index i  0  1   2   3    4    5    6
         2  7  13  19   55   92   99

We try to find the range first (at which spot we divide the array)

2^0 : i=1: A[1] > 19
2^1 : i=2: A[2] > 19
2^2 : i=4: A[4] < 19

Now we know we need to search from index i=0 to i=3.

Now we use binary search for find the element 19

The current subarray we have is

Index i  0  1   2   3   
         2  7  13  19   

Binary search we divide in middle, so we have the array

13 19

Now divide again in middle. 19 is greater than 13 and 19 is only element in array now. We are done, we find 19

Is it correct now?

Answer 1

Steps should increase at exponential stage of searching.

You have to check 1st element of array, then 2nd, then 4th, then 8th, then 16th and so on, until checked element (that has number 2^k) becomes greater (or equal) than value to search.

In this moment you know that searched value is in range 2^(k-1)..2^k, and start binary search at this range

Note that exponential stage allows to find range containing searched value quickly.

P.S. For zero-based array numeration it is convenient to check 0-th index, then start index sequence 1,2,4,8,16...

Answer 2

Exponential search is an algorithm which is used to search through infinite arrays or arrays with unknown size. It has two steps:

1) Search for a position of first element greater or equal than the value 2) Do the binary search from the beginning to the found end

The first step allows you to define the range for a binary search. And due to exponential increasing factor, its called exponential search.