Search in Huge Array

We are trying to search for a target integer, target, in a sorted array of integers (duplicates allowed) that is too big to fit into memory. We can only access the array through an API, fetch(i), which returns the value at index i if i is within bounds or -1 otherwise. Using as few calls to the API as possible, return the index of the target, or -1 if it does not exist. If the target appears multiple times, return any of the indices. There is no API to get the array's length.

Note: In our implementation, fetch is provided as a helper.

1def searchInHugeArray(target: int) -> int:
2    # 1. Find boundaries
3    l, r = 0, 1
4    while fetch(r) != -1 and fetch(r) < target:
5        l = r
6        r *= 2
7        
8    # 2. Binary Search
9    while l <= r:
10        mid = (l + r) // 2
11        val = fetch(mid)
12        if val == -1 or val > target:
13            r = mid - 1
14        elif val < target:
15            l = mid + 1
16        else:
17            return mid
18            
19    return -1
Previous
Search in Sorted Grid
Next
Min-Subarray-Sum Split
l
1
0
r
3
1
5
2
7
3
9
4
11
5
13
6
15
7
17
8
19
9
21
10
23
11
target=13
Step 1 / 6
Step 1:
Exponential Search to find bounds. Start l=0, r=1.
Pointers: l=0, r=1
Focus: select @ [0, 1]
target=13