Exponential binary search

[Omar Sharaki]

I'm trying to apply the exponential binary search, but I'm facing problems regarding the power index. As you know, before I do the normal binary search, I need to keep comparing my key with the elements in my array until I find an element array[2^i] where key<array[2^i]. Then I call binary search with the boundaries 2^(i-1)...2^i. Now, my array contains 676 elements. Which means that starting from i=10, I'm out of the bounds of my array. So if key>array[2^1] and key>array[2^2]....till key>array[2^9], i will be incremented once more to become 10(i.e. 2^10=1024) and the comparison will be done again. But this time, since the array only has 676 elements, I will be out of bounds and I'll get an error. So say the element I'm looking for lies near the end of my array. Then, the first part of the algorithm would probably reach an i greater or equal 10 to find an element greater than my key. This will give me an ArrayOutOfBounds error. So what can one do to avoid this considering that one uses finite arrays? It seems like this is an obvious question to ask regarding the way this algorithm functions, but there doesn't seem to be that much information on it online. Thanks in advance.

[Mike. J. Thompson]

How about you check that the index you want to check is actually in the array before you check it? If you find that 2^i >= array.length then you set the upper boundary to array.length -1.

So your search boundary will either be

2^(i - 1) -> 2^i

Or it will be

2^(i - 1) -> array.length - 1.

Whichever boundaries you have, you perform a binary search on that section of the array and see if the item is in there.