Last Updated: 2 Sep, 2020
Search In Infinite Sorted 0-1 Array
Easy
Asked in companies
You are given an infinite array consisting of only ones and zeroes, in sorted order. You have to find the index of the first occurrence of 1.
Example:
If the array is 0 0 0 0 1 1 1 1… then, the first occurrence of 1 will be at index 4 therefore the answer here is 4.
Note:
As the array size is infinite, the actual array won’t be given to you. Instead, you will be able to access the array elements by calling a method named ‘get’.
get(i) : returns the value present at index I.
Indexing is 0-based.
Instead of representing an infinite array in the input, we give the index of the first occurrence of 1 in the input itself. However, this input will be completely hidden from the user.
It is guaranteed that the answer will fit in a 64-bit integer.
Input Format:
The only input line contains an integer X, the index of the first occurrence of 1. (Hidden to the user)
Output Format:
Print an integer denoting the index of the first occurrence of 1.
Note:
You do not need to print anything, the output has already been taken care of. Just implement the given function.
Constraints:
0 <= ARR[i] <= 1
Time limit: 1sec
Approaches
The simplest approach would be to start from the beginning, i.e. index 0, and check if there’s a 1 at this index. If yes, then we have found the first occurrence of 1. Else, we check for the next index.
Binary search is what comes to mind when we are asked to search for an element in a sorted array. However, there’s a catch: the array size is infinite. How do we apply binary search when we don’t have an upper bound?
If we can’t estimate an upper bound, let’s assume one instead. Let ‘R’ be that index and ‘L’ be the current lower bound. Now, if ‘ARR[R]’ = 0, then we can be certain that all elements from ‘L’ to ‘R’ are 0 (as the array is sorted), hence, we skip this segment, by moving ‘L’s position to ‘R’+1, and setting a new upper bound ('R'). We keep doing this until ‘ARR[R]’ = 1. This means that the first occurrence of 1 lies in the range ['L', ‘R’], and so we binary search in this segment.
This solves our upper bound problem, but there’s another issue: How do we decide the upper bound ‘R’ every time? Let’s look at possible strategies:
We can always set ‘R’ at a constant distance from ‘L’ (let’s say 5). So the jumps we make are [0, 4], [5, 9], [10, 14], and so on. The only problem is, if the first occurrence of 1 is really far away, then this will work no better than a linear search.
Instead of setting ‘R’ at a constant distance, let’s set ‘R’ at 2*'L'-1 every time. So, our jumps would now be [0, 0] (this is an exception), [1, 1], [2, 3], [4, 7], [8, 15], and so on. Notice that our segment sizes increase by a factor of 2 each time. This ensures that we will reach the first index in O(log('X')) time, where ‘X’ is the first occurrence of 1. Once we reach the segment, we simply have to perform a binary search.
Similar problems