GATE CSE 2008 | Question: 40

Question

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

• A. $\Theta(n)$
• B. $\Theta(\log n)$
• C. $\Theta(\log^*n)$
• D. $\Theta(1)$

Comments

😎

---

what is log*n means ?

---

kira204 generally $log^{*}$ is prefered to power of $log$ for ex-$log^{2}n= (logn)^{2}$

Answer 1

Since it is a sorted array, we can use binary search to identify the position of the first occurrence of given integer in  $log(n)$. 

now if integer (appear more than once)repeats, its appearance has to be continuous because array is sorted.

So this is a clear case for asking and applying Binary search.

Answer 2

FOR COMPLETE SOLUTION SEE HERE :

http://www.geeksforgeeks.org/check-for-majority-element-in-a-sorted-array/

Answer 3

Say we need to find the number of occurence of a number k.

If k has to occur atleast n/2 times (that is half of the array size), then k must be there in the middle. There is no way that there are atleast n/2 occurences of k and k is not there in array[middle]. BUT, vice-versa is not true.

Maybe what we can do here is to first look in the condition C1: (array[middle] == k)

If C1 is False, go home.

But if C1 is True we may have something to work with.

Now the n/2 appearances of k will be like a run of k's. Because it is mentioned that we have a sorted array with us. The extremes of the run of k's is what we need to deal with.

Find any one extreme (left or right) of the run of k's. Say you find the index of left extreme(π).

Now to find this value of π we shall use the binary search. This will take T(n) = T(n/2) + 1, T(n) = O (logn).

Now if the run of k's is atleast n/2 then the right extreme must have k as well. (Here WLOG we are assuming that the run is of exactly n/2 length).

right extreme for a run of length n/2(where π is the left extreme of the run) = π+n/2.

Condition C2: ( array[π+n/2] == k)

If C2 is False, it means the run didn't last for n/2 length. Return fail.

If C2 is True, it means k has appeared at least n/2 times in the sorted array.