Search target in unknown-length sorted array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates algorithm design and implementation skills for search algorithms on array-like interfaces with unknown length, focusing on bounds discovery, handling out-of-bounds sentinels, duplicate elements, and rigorous time and space complexity analysis.
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
Input: ([1, 2, 3, 5, 8, 13, 21], 13)
Expected Output: 5
Explanation: 13 sits at index 5; exponential search overshoots past it, binary search pins the exact index.
Input: ([1, 2, 3, 5, 8, 13, 21], 4)
Expected 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
- 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.
- 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.
- 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).
- 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.