Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach.

Approach 2 :  Club binary search approach and array's random access property

Since the array is infinitely increasing i.e. we don't know array size in advance, so we can't directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). We can apply reverse of BinarySearch approach.

We can think of sorted infinite 0 and 1 array as infinite size bit stream on disk with 0 set bits followed by 1 bits.

Approach:
Start with first bit, if it is 1 we are lucky and got the switch index, else if it is 0 check the 2,4,8,16,32,64.... 2^n bits till we get first 1 set bit index say its 'i'. (We are moving by power of 2, rather than 3, 4 etc, because it minimizes the range of data to find the element). Now we have to find between index i/2 to i where the swich happened and this can be done by simple binary search (size of the array to look into is i/2).


Pseudocode:

int GetSwitchIndex()
{
  for(int i=0;;i++)//infinite loop based on break statement
  {
    int arrIndex = power(2,i);
    //lucky case - when first element is lucky
    if(array[arrIndex]==1&&i==0)
      return 0;
    if(array[arrIndex]==1)
      for(int j=arrIndex/2 ; j < arrIndex;j++)
      {
        if(array[j]==1)
          return j;//this is our index
      }
  }//end outer for loop
}

Time Complexity: log(N), N is index at which switch happened.