Exponential search is a searching algorithm that is used to find the position of a target value in a sorted array. It combines two techniques: binary search and an exponential range finding strategy. Exponential search is particularly useful for unbounded or infinite-sized search spaces, although it can also be applied to finite-sized arrays. ### Steps of Exponential Search: 1. **Check the First Element**: Start by comparing the target value with the first element of the array.
Articles by others on the same topic
Exponential search locates a target's possible range in a sorted sequence by probing indices until the target is bounded above or the sequence ends, then uses binary search inside the final bracket. If the target lies near index , this takes probes under random-access and constant-comparison assumptions. For an unbounded monotone predicate, the same method brackets the first true index. It is useful when the relevant prefix is much shorter than the whole sequence or its length is not initially known. Finite sequences still require bounds checks at each probe.