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;
}
preIdx = index;
index *= 2;
}
return
binarySearch(array, value, preIdx, index);
No comments:
Post a Comment