4
$\begingroup$

What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers?

I am trying binary search on the array A.

Algorithm(A):

  1. x = A[mid], where mid is the middle element of the array.
  2. Compare x with A[n/4] and A[3n/4].
  3. If x = A[n/4] and x ≠ A[3n/4] then search in A[1] to A[3n/4 + 1].
  4. If x ≠ A[n/4] and x = A[3n/4] then search in A[n/4 + 1] to A[n].
  5. If x ≠ A[n/4] and x ≠ A[3n/4] then it is a no instance.
  6. If x = A[n/4] and x = A[3n/4] then it is a yes instance.

Running Time: $T(n) = T(3n/4) + O(1)$ which is $O(\log n)$ in asymptotic sense. At each step I am doing two comparisons so $2\log_4n$ if $n = 4^k$. Is there any better (optimal) algorithm to solve the problem mentioned above?

Also, I don't know how to prove the lower bound.

$\endgroup$
2
  • $\begingroup$ It sounds like a good idea, but if I were to give you points for an exercise your solution wouldn't be detailed enough. Try coming up with pseudo code and a proper runtime analysis. To say something about the minimum number required you would also need to give a lower bound proof (that is different from providing an algorithm!). $\endgroup$ – adrianN Dec 21 '16 at 16:16
  • 2
    $\begingroup$ We don't verify answers here. $\endgroup$ – Yuval Filmus Dec 21 '16 at 17:04
5
$\begingroup$

You are asking two questions. I will only answer the second one. Consider the following set of possible inputs: the array is contains either $n/2$ or $n/2+1$ copies of $0$, all elements preceding it are $-1$, and all elements following it are $+1$.

I claim that any algorithm which works correctly for this set of inputs must query, in the YES instances, the first and the last position of the stretch of zeroes. Indeed, if it never queries the first position for example, then the input could have been the NO instance in which the value at that position is replaced by $-1$.

Since the first and last position of zero are at distance exactly $n/2$, and are the only two positions at that distance of equal value, we see that any correct algorithm for your problem can be modified (without any additional comparisons) to give an algorithm for the following problem:

Given an array consisting of $n/2+1$ zeroes, preceded by $-1$ entries and followed by $1$ entries, find the location of the zeroes.

Since there are $n/2$ different answers to this problem, the usual decision tree argument shows that any comparison-based algorithm must make $\log_3 n - O(1)$ three-way comparisons, or $\log_2 n - O(1)$ two-way comparisons of the form "$x=y$ or $x \neq y$?". This shows that for two-way comparisons, your algorithm is nearly optimal. (Note that $2\log_4 n = \log_2 n $.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy