Implement lower_bound on unknown-size sorted array
Overview
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.
Microsoft
Oct 13, 2025, 9:49 PM
Data Scientist
Onsite
Coding & Algorithms
0
0
Lower Bound in Unknown-Length Nondecreasing Array via API
Setup
You are given a non-decreasing integer array A of unknown length n. You cannot access A directly; instead, you have an API:
- get(i): returns A[i] for 0 ≤ i < n; returns +∞ for all i ≥ n.
We define lower_bound(target) as the smallest index i such that A[i] ≥ target. If no such i exists, return −1.
Task
Implement lower_bound(target) with the following constraints and deliverables:
-
Algorithm
- Use exponential search to bracket the answer, then binary search to find the exact index.
- Overall time must be O(log n) and the number of get calls should also be O(log n).
-
Edge cases to handle
- Duplicates in A.
- Empty array (n = 0).
- All values in A < target.
- All values in A ≥ target.
-
Analysis
- Prove correctness (why the algorithm returns the smallest index with A[i] ≥ target or −1 correctly).
- Give a tight upper bound on the number of get calls (as a function of n and, where natural, of the answer index).
-
Variant
- Explain how your approach changes if A is non-decreasing but may be rotated once (e.g., [4,5,6,1,2,3]), both without and with duplicates.
Solution
Login required
Show