madeeasy theory book closed

Question

a sorted array of n elements contains 0 and 1. to find out majority of 0 and 1 how much ime it will take?

1)O(1)

2)O(logn)

3)O(n)

4)O(n^2)

Answer 1

As the array elements are previously sorted ,we will check for middle elements of the array only, i.e:

If n is odd then we will check for (n/2)th element (element at the center) and if it is 0 then 0 is in majority , otherwise 1 is in majority.

if n is even then we will first check for (n/2)th element and if it is 0 then 0 is in majority and if it is 1 then we will check for (n/2-1)th element , if it is 1 then 1 is in majority. 

In both cases number of comparison required are of O(1)

Hence 1) is the correct answer...

Comments

The array will contain 0 and 1. But, how are we certain that the array will contain only 0 and 1?

Answer 2

we can do it using binary search..so i think it should be O(logn)..please correct me if i am wrong

Comments

It should b O(1).

---

How?? Can you please explain.