AK
BAN USERSince the array is infinitly increasing i.e. we don't know arrry size in advance, 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'. 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.
@Anonymous
- AK July 12, 2011Solution looks good but your code will visit all the nodes in the tree even if it found the second largest element much earlier.