702. Search in a Sorted Array of Unknown Size
Problem Description
In this interactive problem, you are given access to a sorted array of unique elements, but you do not know its size. To interact with this array, you can use the ArrayReader
interface, which has a function get(i)
that will return the value at the ith index (0-indexed) if it's within the bounds of the array. If i
is outside the bounds of the array, get(i)
will return 2^31 - 1
, which serves as an indication of being outside the array’s boundaries.
You are also provided an integer target
, and your task is to find the index k
in the hidden array where secret[k] == target
. If the target is not present in the array, you should return -1
. The requirement is to accomplish this with a solution that has a runtime complexity of O(log n), which implies that a binary search algorithm should be used.
Intuition
Since we don't know the array's size, we can't directly apply binary search. However, the problem statement helps by stating that the ArrayReader.get(i)
function will return a very large number (specifically, 2^31 - 1
) if we access an index beyond the array's bounds. This allows us to first locate the possible range where the target could reside.
To find this range, we could intuitively start with an initial guess and then expand our search range exponentially until we find an out-of-bound value. Once we identify an index that returns an out-of-bound value, we know that the array's size is less than this index. We could then perform a binary search between the start of the array and the identified out-of-bound index.
The solution code, however, does not initially find the bounds of the array. Instead, it assumes a range of indexes between 0
and 20,000
, which should be more than enough to cover typical constraints of the problem since we are told that get(i)
will return 2^31 - 1
for out-of-bound accesses. With this assumption, the solution applies a binary search algorithm right away.
During the binary search, if reader.get(mid)
is greater than or equal to target
, it means the target is located at mid
or to the left of mid
(since the array is sorted), so it narrows the search range's upper bound to mid
. If reader.get(mid)
is less than target
, the target can only be to the right of mid
, and it narrows the search range's lower bound to mid + 1
. This process is repeated until the lower and upper bounds converge to the smallest range possible that might contain the target.
Finally, having honed in on a potential index where target
could exist, the solution checks if reader.get(left)
is indeed equal to target
. If it is, left
is returned as the index where target
was found. If reader.get(left)
does not match target
, the function returns -1
, indicating that the target is not in the array.
Learn more about Binary Search patterns.
Solution Approach
The solution uses a variation of binary search to efficiently find the target
value within a sorted array of unknown size. Binary search is a divide-and-conquer algorithm that operates by repeatedly dividing in half the portion of the list that could contain the item, until there are no more segments left or the item is found.
In the standard binary search, the middle element is typically compared to the target value, and based on that comparison, you can decide if the target would be in the left half or the right half of the current segment.
Here's how the implemented solution strategically applies binary search to the given problem:
-
Initial Range Setting: Given that the exact size of the array is unknown, the solution begins by setting a broad search range for the binary search, with
left
set to 0 andright
set to 20,000. Since we knowArrayReader.get(i)
will return a very large number (specifically2^31 - 1
) ifi
is out of the array bounds, this large upper bound is safe to assume for most inputs as per problem constraints. -
Binary Search Application: While
left
is less thanright
, the solution continuously narrows the search range based on the value returned by theArrayReader.get(mid)
:- If
ArrayReader.get(mid)
is greater than or equal to thetarget
, it means thetarget
cannot be to the right ofmid
(since the array is sorted), so the upper bound of the range (right
) is set tomid
. - If
ArrayReader.get(mid)
is less than thetarget
, then thetarget
must be to the right ofmid
, and thus the lower bound of the range (left
) is set tomid + 1
.
To find the
mid
index, the average ofleft
andright
is calculated using(left + right) >> 1
, which is equivalent to(left + right) / 2
but is often faster in many programming languages due to bit shifting. - If
-
Target Verification: After exiting the while loop, the
left
variable should either be at the location of thetarget
value or at the smallest index greater than thetarget
. To verify whether thetarget
has been found,ArrayReader.get(left)
is compared to thetarget
:- If they match, the index
left
is returned, indicating the location of thetarget
. - If they do not match, it means the
target
is not present in the array, so-1
is returned.
- If they match, the index
It's important to understand that binary search reduces the search space by half with each step, leading to the O(log n) runtime complexity, which is a requirement as per the problem.
Moreover, in practice, an initial range could be determined dynamically by starting with a small range and exponentially expanding it (doubling it each time) until an out-of-bound access occurs. This step can optimize the solution further if the potential maximum size of the array is significant compared to the actual size of the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have an ArrayReader
that provides access to a sorted array: [3, 5, 7, 10, 15, 20]
. We don't know the size of this array, but we need to find the index of the target
value 10
using the solution approach described.
Here's how the solution would work with this example:
-
Initial Range Setting: We start by establishing an initial large search range for the binary search. We set
left
to0
andright
to20,000
. -
Binary Search Application: Now we begin the binary search process.
-
Start Loop:
- Calculate
mid
as(left + right) >> 1
, which is initially(0 + 20,000) >> 1 = 10,000
. - Check
ArrayReader.get(10,000)
, it returns2^31 - 1
, which means10,000
is out of the array bounds. Since the value is very high, we set the value ofright
tomid
, which is now10,000
. - Recalculate
mid
as(0 + 10,000) >> 1 = 5,000
, and so on, until we get to amid
value inside the bound of the array.
Continue the loop with
left
set to0
andright
set now to an index within the array bounds. For this example, let's assume that after several steps (not shown for brevity), we have narrowed down the bounds toleft = 2
andright = 5
.mid
is(2 + 5) >> 1 = 3
.ArrayReader.get(3)
returns10
, which is the target value.- Since
ArrayReader.get(mid) == target
, the search is over, and we skip to theTarget Verification
step.
- Calculate
-
End Loop.
-
-
Target Verification: We verify the value found at the index
3
to ensure it is indeed thetarget
.ArrayReader.get(3)
is equal to10
, which matches thetarget
.- We return the index
3
because this is where thetarget
was found.
In this example, after several iterations of narrowing the search bounds and recomputing mid
, we have successfully found the target value of 10
at index 3
using binary search. This demonstrates the efficiency of binary search in reducing the search range quickly compared to a linear search, meeting the complexity requirement O(log n).
Solution Implementation
1class ArrayReader:
2 def get(self, index: int) -> int:
3 pass # Placeholder for the get method of ArrayReader.
4
5
6class Solution:
7 def search(self, reader: ArrayReader, target: int) -> int:
8 """
9 Search for a target value in a sorted array of unknown length.
10
11 We use a binary search approach, defining the initial range based
12 on given constraints (here 0 to 20000).
13
14 Parameters:
15 reader (ArrayReader) - an instance of ArrayReader to access array elements
16 target (int) - the target value to search for
17
18 Returns:
19 int: The index of the target value or -1 if the target is not found.
20 """
21
22 # Initialize the left and right pointers for binary search.
23 left, right = 0, 20000
24
25 # Perform binary search within the bounds of left and right.
26 while left <= right:
27 # Calculate the middle index.
28 mid = left + (right - left) // 2
29 # Retrieve the value at the middle index from the reader interface.
30 mid_value = reader.get(mid)
31
32 # If the middle value matches the target, return the index.
33 if mid_value == target:
34 return mid
35 # If the middle value is greater than the target, adjust right boundary.
36 elif mid_value > target:
37 right = mid - 1
38 # If the middle value is less than the target, adjust left boundary.
39 else:
40 left = mid + 1
41
42 # If the loop ends and we haven't returned, the target is not in the array.
43 return -1
44
45# Please note that the ArrayReader class is not fully implemented above.
46# It only serves a placeholder to illustrate how the get method signature should look.
47# Since the original problem was rewritten to match Python 3 syntax and best practices,
48# real implementation of get method from ArrayReader class or real input would be required to run the code.
49
1/**
2 * This is the implementation of a solution for finding the target element
3 * in a sorted array with unknown size using an API provided by ArrayReader.
4 */
5class Solution {
6
7 /**
8 * Searches for the target value in a sorted array with unknown size.
9 * @param reader An object with an API to get elements at a specific index.
10 * @param target The value to search for in the array.
11 * @return The index of the target if found, otherwise returns -1.
12 */
13 public int search(ArrayReader reader, int target) {
14 // Initialize the left pointer at the start of the array.
15 int left = 0;
16 // Initialize the right pointer with a high enough index to ensure the target is within range.
17 // The value 20000 is used as an arbitrary high index; in practice, this should cover the array length.
18 int right = 20000;
19
20 // Binary search algorithm to find the target value.
21 while (left < right) {
22 // Calculate the mid index by averaging left and right, shifting right by 1 avoids potential overflow.
23 int mid = left + (right - left) / 2;
24 // If the value at mid is greater than or equal to the target, narrow the search to the left half.
25 if (reader.get(mid) >= target) {
26 // Update the right boundary to mid, as the target can either be at mid or to the left of mid.
27 right = mid;
28 } else {
29 // Update the left boundary to mid + 1, excluding mid from the next search range.
30 left = mid + 1;
31 }
32 }
33 // After the loop, left should point to the target if it exists. Return the index if the target is found.
34 return reader.get(left) == target ? left : -1;
35 }
36}
37
1/**
2 * This function searches for a target element in a sorted array with unknown size.
3 * The ArrayReader API is used to access elements by index without knowing the array's length.
4 *
5 * @param reader The array reader that provides access to the elements.
6 * @param target The target value to search for in the array.
7 * @return The index of the target if found, otherwise -1.
8 */
9class Solution {
10public:
11 int search(const ArrayReader& reader, int target) {
12 // Initialize boundaries left and right.
13 // The right boundary is set to 20000 as the problem statement indicates that
14 // array values will be less than 10000, so 20000 is safely outside the range.
15 int left = 0;
16 int right = 20000;
17
18 // Run binary search algorithm to find the position of the target.
19 while (left < right) {
20 // Calculate the midpoint of the current left and right boundaries.
21 int mid = left + (right - left) / 2; // Use a different method to avoid potential overflow.
22
23 // Get the value at the midpoint index from the reader.
24 int val = reader.get(mid);
25
26 // If the midpoint value is greater than or equal to the target, move the right boundary to mid,
27 // otherwise, move the left boundary to mid + 1.
28 if (val >= target) {
29 right = mid;
30 } else {
31 left = mid + 1;
32 }
33 }
34
35 // Once the search is over, check if the left boundary is at the target's position
36 // by comparing the value at left's index to the target value.
37 // Return the index if it's the target, or -1 if not.
38 return reader.get(left) == target ? left : -1;
39 }
40};
41
1/**
2 * Interface representing an array reader that supplies a `get` method to access elements at a given index.
3 */
4interface ArrayReader {
5 get(index: number): number;
6}
7
8/**
9 * Searches for a target element in a sorted array with an unknown size using the ArrayReader.
10 * Implements a binary search algorithm assuming a very large array where negative elements
11 * denote the sequence has ended.
12 *
13 * @param reader - The array reader providing access to elements.
14 * @param target - The target value to search for.
15 * @returns The index of the target if found, otherwise -1.
16 */
17function search(reader: ArrayReader, target: number): number {
18 let left: number = 0;
19 // Artificially setting the right boundary very high since the array size is unknown,
20 // but we know the range of possible values based on the problem constraints.
21 let right: number = 20000;
22
23 while (left < right) {
24 // Calculate the middle index to partition the array into halves.
25 let mid: number = left + Math.floor((right - left) / 2);
26
27 // Retrieve the value at the middle index using the reader.
28 let valueAtMid: number = reader.get(mid);
29
30 if (valueAtMid >= target) {
31 // If value at mid is greater or equal to the target, we shrink the right boundary.
32 right = mid;
33 } else {
34 // If value at mid is less than the target, we adjust the left boundary.
35 left = mid + 1;
36 }
37 }
38
39 // After exiting the loop, left should be at the smallest index whose value is at least the target.
40 // Check if the actual value at the index is equal to the target and return the index if so.
41 return reader.get(left) === target ? left : -1;
42}
43
44// Example usage:
45// Assume there exists an ArrayReader instance - someReader,
46// and a target value - targetValue.
47// You can call the search function as follows:
48// const index: number = search(someReader, targetValue);
49
Time and Space Complexity
The time complexity of the provided code is O(log n)
where n
represents the position of the target value or the position where the reader's get method returns INT_MAX
signaling the end of the array. This is due to the binary search approach where the space to be searched is halved at each iteration.
The space complexity is O(1)
since the algorithm uses a constant amount of extra space, with variables like left
, right
, and mid
that do not depend on the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.