AlgoVisual | See the logic

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

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

19 return -1

Search in Huge Array

Reference solution