in Algorithms edited by
23,705 views
68 votes
68 votes

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

  1. $\Theta(n)$
  2. $\Theta(\log n)$
  3. $\Theta(\log^*n)$
  4. $\Theta(1)$
in Algorithms edited by
23.7k views

4 Comments

If an element occurs more than n/2 times, it WILL be present in the middle of the sorted array.

 

Now, counting the occurrences in a sorted array can easily be done by binary search.

We need to find boundary indices.

 

We can intuitively do it by performing a linear search on left and right directions to find the boundary indices. But, this takes linear time in the worst case (all elements are same)

 

Better way is to delete the equality condition from the binary search algorithm.

ie, delete a[k] = x method.

Now, we're only left with a[k] > x and a[k] < x.

Now, instead of returning -1 on an unsuccessful search, return i

We can do manipulations like these to get a boundary index.

Then, reverse this algo to get the other boundary index.

Subtract both these indices to check if the value is $\geq n/2$
0
0
Can anyone plz explain with giving a better example? I'm not getting it .Plz explain it with the better example
0
0

7 Answers

1 vote
1 vote

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.

0 votes
0 votes
0 votes
0 votes
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.
Answer:

Related questions