Given an input array of size unknown with all 1's in the beginning and
0's in the end. Find the index in the array from where 0's start,
consider there are millions of 1's and 0's in the array .i.e array is
very big e.g array contents 1111111.......1100000.........0000000
Since the array is infinitly increasing i.e. we don't know arrry 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).
Time Complexity: log(N), N is index at which switch happened.
An even faster solution would be to use bit operators as they are faster so instead of comparing with you could XOR with 1 and the index where it gives a 0 on XORing is the required index where first 0 is present.
Strategy:
Since the array is infinitly increasing i.e. we don't know arrry 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).
Time Complexity: log(N), N is index at which switch happened.
An even faster solution would be to use bit operators as they are faster so instead of comparing with you could XOR with 1 and the index where it gives a 0 on XORing is the required index where first 0 is present.
No comments:
Post a Comment