This is an interactive problem.
You have a sorted array of unique elements and an unknown size. You do not have an access to the array but you can use the ArrayReader interface to access it. You can call ArrayReader.get(i) that:
ith index (0-indexed) of the secret array (i.e., secret[i]), or231 - 1 if the i is out of the boundary of the array.You are also given an integer target.
Return the index k of the hidden array where secret[k] == target or return -1 otherwise.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: secret = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in secret and its index is 4.
Example 2:
Input: secret = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in secret so return -1.
Constraints:
1 <= secret.length <= 104-104 <= secret[i], target <= 104secret is sorted in a strictly increasing order.Problem Overview: You need to search for a target value in a sorted array, but the array length is unknown. Instead of direct indexing, you access elements through an API like reader.get(i). If you read beyond the array boundary, the API returns a very large sentinel value. The challenge is locating the search boundaries before applying binary search.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest approach is to start from index 0 and keep calling reader.get(i) while incrementing the index. Stop when the value equals the target or exceeds it. Because the array is sorted, once the returned value becomes larger than the target (or the sentinel value appears), the target cannot exist further. This approach works but is inefficient for large arrays because it may require scanning many elements sequentially.
Approach 2: Exponential Range Expansion + Binary Search (O(log n) time, O(1) space)
The efficient solution first discovers a valid search window using exponential expansion. Start with a small range such as [0, 1]. While reader.get(right) < target, double the right boundary (right *= 2). This quickly jumps across the array until the range contains the target or exceeds it. After identifying a range where the target could exist, run standard binary search between left and right.
Binary search repeatedly checks the middle index and narrows the search interval depending on whether the middle value is smaller or larger than the target. Because the array is sorted and the boundary was discovered through exponential growth, the search converges in logarithmic time.
This method combines two classic ideas: exponential search to determine bounds and binary search to locate the exact position. The algorithm only uses constant extra memory and interacts with the array through the provided interface, which makes it suitable for array-based search problems with hidden sizes.
Recommended for interviews: Exponential expansion followed by binary search is the expected approach. A quick mention of the linear scan demonstrates understanding of the problem constraints, but interviewers look for the logarithmic solution because it handles very large arrays efficiently and shows strong mastery of binary search patterns.
First, we define a pointer r = 1. Each time, we check if the value at position r is less than the target value. If it is, we multiply r by 2, i.e., shift it left by one bit, until the value at position r is greater than or equal to the target value. At this point, we can determine that the target value is within the interval [r / 2, r].
Next, we define a pointer l = r / 2, and then we can use the binary search method to find the position of the target value within the interval [l, r].
The time complexity is O(log M), where M is the position of the target value. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple baseline when array size is small or when demonstrating brute force thinking |
| Exponential Range Expansion + Binary Search | O(log n) | O(1) | Optimal approach when array size is unknown and values are sorted |
LEETCODE 702 (JAVASCRIPT) | SEARCH IN A SORTED ARRAY OF UNKNOWN SIZE • Andy Gala • 2,385 views views
Watch 9 more video solutions →Practice Search in a Sorted Array of Unknown Size with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor