The Unbounded Array: Search Without Knowing the Size

In the mysterious Infinite Corridor of Prime City, the Explorer encounters a sorted array of unknown size. The array is represented as a function that returns the element at index i, or infinity if i is beyond the array's bounds. The Explorer must find a target value using exponential search. "Since we don't know the size," the Explorer says, "we double the index until we either find the target or go past it. Then binary search in the identified range." Given a sorted array of N integers (but N is not provided to your algorithm) and a target T, find the index of T. The array is accessible via a function get(i) which returns array[i] if i < N, or 10^18 (infinity) if i >= N. For this problem, the input provides N and the array, but your solution should work without knowing N in advance. Output the index of T, or -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 10 20 30 40 50 25 Output: -1