Dark Mode

25,523 views

70 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

- $\Theta(n)$
- $\Theta(\log n)$
- $\Theta(\log^*n)$
- $\Theta(1)$

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$

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

67 votes

Best answer

Answer is **option B.**

whenever there exists an element which is present in the array : more than $\frac{n}{2}$ times, then definitely it will be present at the middle index position; in addition to that it will also be present at anyone of the neighbourhood indices namely $i-1$ and $i+1$

No matter how we push that stream of **More than** $\frac{n}{2}$ times of elements of same value around the Sorted Array, it is bound to be present at the middle index $+$ atleast anyone of its neighbourhood

once we got the element which should have occurred more that $n/2$ times we count its total occurrences in $\mathcal{O}(\log n)$ time.

1

5

suppose

1 3 4 4 4 4 4 6 7 9

4 occurs in middle but not majority by n/2

it is present both in middle as well as the neighbourhood.

The algo checks to find the position of frst occurance of 4.

here for 4 it is,3

>n/2 times means

there should be span of n/2 4 s,since element are in sorted order,nothing between span of 4 s.

Hence,i+n/2 th index must also be 4 .here it is not ,so here 4 is not occurring > n/2

core of the algo is a BS which is logn

1 3 4 4 4 4 4 6 7 9

4 occurs in middle but not majority by n/2

it is present both in middle as well as the neighbourhood.

The algo checks to find the position of frst occurance of 4.

here for 4 it is,3

>n/2 times means

there should be span of n/2 4 s,since element are in sorted order,nothing between span of 4 s.

Hence,i+n/2 th index must also be 4 .here it is not ,so here 4 is not occurring > n/2

core of the algo is a BS which is logn

25

1

0

7

Actually in the sorted array if an element is present more than than n/2 times then it must be present in the middle element so in a sorted array we can find in O(1) time and to locate the element where it ends and where it starts we have to take a binary search which is O(log n) time so total O(log n) time.

30

edited
Dec 23, 2016
by Sachin Mittal 1

Does Divide and Conquer work here ?

I know I have to count occurrences of middle element.

I will divide array into two halves, then i will count occurrance of that element indivisually, then i will combine and check if total occurance if greater than n/2 or not.

Like this

mid=n/2 Count_occurrance(i,j) { if(i==j && A[i] == A[mid]) return 1; if(i==j && A[i] != A[mid]) return 0; else if (A[(i+j)/2] = A[mid]) return(1+Count_occurrance(i, k)+Count_occurrance(k+1,j)) //here k is (i+j)/2 else return(Count_occurrance(i, k)+Count_occurrance(k+1,j)) }

this is

T(n) = 2T($\frac{n}{2}$)+c

which gives $logn$.

Is this ok ?

13

0

@Chhotu See first of all how to get the element that must have occurred more than n/2 times?

Tell me that.

Sol:: It takes O(lgn) time

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

Tell me that.

Sol:: It takes O(lgn) time

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

7

0

0

@ Chhotu @Vs

Why are we searching for x in the middle position ?

As per question,* If an integer appears more than n/2 times,*so does this mean our function will take integer and check if it is occurring more than n/2. Or does this mean we need to check if there exists such integer?I interpreted as the former way but the answer assume as per later way.Please clear this

0

0

Sir doesn't minimum number of comparisons mean that we have to consider the best case.In best case we have to check the middle element,both the first and last element.Suppose the element is present in last index then we simply need to check the element before the middle element to see if the element is occurring more than **n/2 **or not.So the best case number of comparisons should be constant.so,omega(1).correct me if I am wrong.

1

@Sachin Mittal 1 sir,

I think Divide and Conquer would take O(n). and not O(logn). see by Masters theo.

1

@shubham0109

It's iterated logarithm.

See here: https://en.wikipedia.org/wiki/Iterated_logarithm

Also present in Cormen.

0

@Sachin Mittal 1 sir,

in your code

else if (A[(i+j)/2] = A[mid]) return(1+Count_occurrance(i, k)+Count_occurrance(k+1,j)) //here k is (i+j)/2 else return(Count_occurrance(i, k)+Count_occurrance(k+1,j))

here in **else** we can simply **return 0 **because if that element is not present in the mid position then it is obviously not having more than **n/2** occurrance’s .

please check once!

0

64 votes

The starting position of required element can be anywhere between

1 to n/2-1(inclusive).

We have to search that elements starting index to do that Modified Binary Search.

Step1--ELE=A[n/2]

Step2:--Search for starting index of ELE with in range of 1 to n/2-1 which is sorted array. O(logn) time cost of modified binary search.

Now after find such index say i Now see if A[i] ==A[ i+ n/2 ] then it is the majority Ele (Cz Sorted array) else no majority Ele present. Above done in O(1).

So overall time complexity O(logn)+O(1)=O(logn)

Hence Option B is Ans.

1 to n/2-1(inclusive).

We have to search that elements starting index to do that Modified Binary Search.

Step1--ELE=A[n/2]

Step2:--Search for starting index of ELE with in range of 1 to n/2-1 which is sorted array. O(logn) time cost of modified binary search.

Now after find such index say i Now see if A[i] ==A[ i+ n/2 ] then it is the majority Ele (Cz Sorted array) else no majority Ele present. Above done in O(1).

So overall time complexity O(logn)+O(1)=O(logn)

Hence Option B is Ans.

51 votes

To check whether a given number is repeated n/2 times in the array can be done in O(log n) time.

Algo

1. find the **first** occurrence (index i) of x(given number) in the array which can be done in O(log n) time (a variant of binary search).

2. check if A[i] == A[n/2+i]

return true

3. else return false

3 votes

Fool proof way to find is, to perform 2 binary searches, one for n-1 and other for n+1.

Even if n-1 and n+1 are not present, we can modify BST to return the index where min,max are equal.

Then check the difference between two resuls, if greater than n/2.

Hence 2logn comparisons required and **answer is B**.