The Galloping Search: Find an Element in a Sorted Array

In the vast library of Prime City, the Search Master uses exponential search (also called galloping search) to find elements in sorted arrays. The algorithm first finds a range where the target might exist by doubling the index, then performs binary search within that range. "Exponential search is ideal for sorted arrays of unknown or very large size," the Search Master says. "Start at index 1, double the index until you overshoot the target, then binary search between the previous index and the current one." Given a sorted array of N integers and a target T, find the index of T using exponential search. If T is not found, output -1. Constraints: 1 <= N <= 10^5, -10^9 <= array[i], T <= 10^9, sorted non-decreasing Input: 7 1 3 5 7 9 11 13 9 Output: 4 Input: 5 2 4 6 8 10 5 Output: -1