Find the start index of 1 in infinite length sorted array of 0s and 1s

Given an infinite size array with only 0s and 1s and sorted. Find the transition point where 0s end or 1s start.

Approach#1

We cannot apply the Simple Binary as the length of Array is not given.

So we need to apply the linear search.

Complexity: O(n) where n may be infinite.

Approach#2

Use Binomial theorem to find the index (simulate the Binary Search).

1. At first check the 2^i the index i=0,1,2,....

2. If '1' occurs at some point of index [example say 32 i.e. 2^5]

3. Apply binary search between 2^4 and 2^5. (Now we have two indexes to apply Binary search).

Complexity: O(logn).

Pseudo code:

array[1....inf]

preIdx = 0;
index=1;

while(array[index]!=1) {
           preIdx = index;
           index *= 2;
}

return binarySearch(array, value, preIdx, index);