Implement lower_bound on unknown-size sorted array
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given a non-decreasing integer array A of unknown length, accessible only via API get(i) that returns +∞ for i ≥ n, implement lower_bound(target): the smallest index i with A[i] ≥ target, or −1 if none exists. Use exponential search to bracket n and then binary search to find the answer with overall O(log n) time. Handle duplicates, empty array, all values < target, and all values ≥ target. Prove correctness, give a tight upper bound on the number of get calls, and explain how your approach changes if A may be rotated once (with or without duplicates).
Quick Answer: This question evaluates ability to design efficient search algorithms for unknown-length non-decreasing arrays accessed via a limited get(i) API, emphasizing correctness proof and tight query/time complexity bounds.
You are given a non-decreasing (sorted ascending, duplicates allowed) integer array `A`. Implement `lowerBound(A, target)` that returns the smallest index `i` such that `A[i] >= target`. If no such index exists, return `-1`.
The intended algorithm models an array of *unknown* length accessed only through an API `get(i)` that returns `A[i]` for valid indices and `+infinity` for `i >= n`. You should bracket the answer with **exponential search** (double an upper bound until the value at that index is `>= target`, which also triggers when the index passes the end of the array) and then **binary search** within the bracket for the first index whose value is `>= target`. Both the running time and the number of `get` probes must be `O(log n)`.
Handle these cases: duplicate values, an empty array, every value strictly less than `target` (answer `-1`), and every value already `>= target` (answer `0`).
Example: `A = [2, 3, 5, 7, 9]`, `target = 6` -> the first element `>= 6` is `7` at index `3`, so return `3`.
Constraints
- 0 <= n = len(A) <= 10^6
- A is sorted in non-decreasing order (duplicates allowed)
- -10^9 <= A[i], target <= 10^9
- Must run in O(log n) time and use O(log n) get-style probes
- Return -1 when no index satisfies A[i] >= target (including the empty array)
Examples
Input: ([2, 3, 5, 7, 9], 6)
Expected Output: 3
Explanation: First element >= 6 is 7 at index 3. Exponential search brackets (2,4], binary search lands on index 3.
Input: ([1, 2, 2, 2, 5], 2)
Expected Output: 1
Explanation: Duplicates: the smallest index with value >= 2 is index 1 (the first 2), not index 2 or 3.
Hints
- Frame it as a monotone predicate f(i) = (A[i] >= target), treating A[i] = +infinity for i >= n. f is False for i < i* and True for i >= i*, so you are searching for the first True index.
- Phase 1 (exponential search): start hi = 1 and double it until get(hi) >= target. Because out-of-range indices return +infinity, this loop always terminates with f(lo)=False and f(hi)=True, even when the answer is past the end of the array.
- Phase 2 (binary search): with the invariant f(lo)=False and f(hi)=True, halve the interval until lo+1 == hi; then hi is the first True index. Cache the value at hi so that if it is +infinity (index passed the end) you can return -1 without an extra probe.