Search target in unknown-length sorted array

You have read-only access to a sorted, increasing array-like interface of unknown length that supports get(i), which returns a valid integer for in-bounds i and a sentinel (e.g., +∞ or None) when i is out of bounds. Given a target value k, design an algorithm to find the index of k if it exists, otherwise return −1. Optimize time complexity, describe the approach to discover an upper bound, and handle duplicates by returning the first occurrence. Analyze time and space complexity.

Search Target in Unknown-Length Sorted Array

You are given read-only access to a sorted, strictly-or-non-strictly increasing array-like interface of UNKNOWN length. The only operation available is get(i): it returns the integer at index i for in-bounds i, and a sentinel (here modeled as None / out-of-bounds) for any i beyond the array. Given a target value k, return the index of k if it exists, otherwise return -1. Optimize time complexity (you may not call len()): first discover an upper bound on the valid index range using exponential (galloping) search — start at index 1 and double until get(index) is out of bounds OR get(index) >= k — then binary search within that window. Handle duplicates by returning the FIRST (smallest) index whose value equals k.

For this executable console the interface is provided concretely: solution(arr, k) receives the backing list arr and the target k, but the algorithm must behave as if it can only probe via get(i) (no len() short-circuit on the search itself).

Return the first index of k, or -1 if k is not present.

Constraints

• The array is sorted in non-decreasing order.
• Length is unknown; only get(i) may be used to probe (out-of-bounds returns a sentinel).
• Values and the target k fit in a 32-bit signed integer.
• 0 <= conceptual length <= 10^9 (algorithm must not depend on knowing it).
• Duplicates may exist; return the smallest index whose value equals k.
• Return -1 if k is not present.

Examples

Example 1

Input: ([1, 2, 3, 5, 8, 13, 21], 13)
Output: 5

Explanation: 13 sits at index 5; exponential search overshoots past it, binary search pins the exact index.

Example 2

Input: ([1, 2, 3, 5, 8, 13, 21], 4)
Output: -1

Explanation: 4 is absent; binary search lands on the first value >= 4 (which is 5), and since 5 != 4 it returns -1.

Hints

1. You cannot call len(). To bound the search space, start at index 1 and keep doubling (1, 2, 4, 8, ...) until get(index) is out of bounds OR get(index) >= k. The previous index is a safe lower bound.
2. Out-of-bounds probes should behave like +infinity: they are 'greater than or equal to' any target, so binary search pushes them to the right side.
3. To return the FIRST occurrence among duplicates, run a 'leftmost' binary search: when value >= k, record the index and keep searching the LEFT half (right = mid - 1).
4. After binary search lands on the first index with value >= k, verify that value actually equals k — if it's strictly greater (or out of bounds), k is absent, so return -1.