Exponential Search Algorithm

Exponential search finds a target value in a sorted, unbounded or very large array by first determining a range that must contain the target, doubling an index repeatedly, one, two, four, eight and so on, until the value at that index exceeds the target or the array's end is reached, and then performing a binary search within the identified range. It runs in O(log i) time where i is the position of the target, especially useful when the target is expected to be near the beginning of the array or when the array's length is not known in advance, such as searching an unbounded list. Jon Bentley and Andrew Chi-Chih Yao described the technique in 1976.