Binary Stream

Question

We have a run of 0's followed by the run of 1's and we have to find the point where first 1 will be present. We only know the start of the sequence but we have no idea about the end.

what should the best case complexity of this problem? Describe your approach.

Comments

We will have to go in serial fashion, traversing one element after another until we find the $1$. So complexity would be O(Num_Zeros). There isn't any best case complexity I can think of. O(Num_Zeros) is the complexity for best / avg / worse case

---

we can also us binary search to find first 1.then that will take less time

---

@Akriti, I had also thought so, but we don't know end of list, so binary search not possible

---

oo i did nt notice that fact..thankyou:)

Answer 1

It can be done in O(log n)

first we search a[2] if not equal to 1 then a[4],a[8], a[16]....

we use two variables for this one which stores a[2^n-1] and another which stores a[2ⁿ]

let us say that at a[1024]=0 and a[2048]=1

now we have a low and a high now we can apply binary search

complexity

traversing in power of 2 = (log n)

binary search  = (log n)

total complexity(log n + log n)=O(log n)

Comments

cool one. :)  +1