**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