Efficient Search Using Exponential Search

You are given an array of n distinct integers sorted in non-decreasing order, which may be very large, and a target value x. Implement exponential search: starting from index 1, repeatedly double a bound index while the element there is smaller than x, in order to quickly find a range that must contain x (if it exists), then run a plain binary search restricted to that range. Output the 0-based index of x if it is present, otherwise output -1.

Input: The first line contains the integer n. The second line contains n space-separated strictly increasing integers. The third line contains the integer target x. Output: Print a single integer: the 0-based index of x in the array, or -1 if x is not present.

1 <= n <= 10^6 Array elements are strictly increasing (all distinct) -10^9 <= a[i], x <= 10^9

Exponential search's real value isn't asymptotic (it's still O(log n) overall) - it's about being FASTER IN PRACTICE for targets near the front, and being APPLICABLE at all when the array's total size isn't known in advance, unlike plain binary search.

Search a sorted array by doubling a bound index to quickly find a range containing the target, then binary search within that range. Brute force: Run a plain binary search over the ENTIRE array from the start - this is already O(log n), but exponential search can be FASTER in practice when the target is near the FRONT of a very large (or even unbounded-length) array, since it doesn't need to touch far-away elements to establish initial bounds. Optimised: Doubling the bound index finds a range containing the target in O(log(position of target)) steps rather than O(log n) steps based on the WHOLE array's size - this is a genuine improvement when the target's position is much smaller than n, and is especially valuable for searching structures where the total size isn't even known upfront (like an unbounded stream).

1. Starting from index 1, repeatedly DOUBLE a bound index (1, 2, 4, 8, ...) WHILE the element there is smaller than the target. 2. Once doubling stops (the bound's element is no longer smaller than the target, or you've run off the end), you have a range AT MOST as wide as the last doubling step. 3. Run a plain BINARY SEARCH restricted to just that range; clamp the upper end to the array's last valid index before searching.

Time: O(log(position of target)) to find the bounding range, plus O(log(range width)) for the final binary search - both bounded by O(log n) overall, but often faster in practice for targets near the front. Space: O(1) - just a few index variables.

The target may be the very first element (index 0), the very last element, or absent from the array entirely; n may be as small as 1.

Be ready to mention the specific use case where exponential search shines: searching an array of UNKNOWN or UNBOUNDED size, where a plain binary search couldn't even establish its initial search range without knowing n upfront.