1
$\begingroup$

Given a sorted array of integers and a target integer, find the number of occurrences of the target integer.

It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the size of the array. For example, given an array $[1,2,3,3,4,5]$ and a target $3,$ the algorithm should return $2$ since there are two copies of $3$ in the array.

Question: Is there a faster algorithms which has time complexity less than $O(\lg n)?$ Otherwise, is there a proof to prove that $\Omega(\lg n)$ is the theoretical lower bound?

$\endgroup$
  • $\begingroup$ You should use $\Omega(\log n)$, instead of $O(\log n)$ when describing lower bound in your situation. $\endgroup$ – hengxin Jun 6 at 3:17
  • $\begingroup$ @hengxin Thanks for pointing out. Edited my question. $\endgroup$ – Idonknow Jun 6 at 4:15
4
$\begingroup$

The problem requires $\Omega(\log n)$ accesses to memory even if you are promised that the target integer appears at most once. You can prove it using an adversary argument.

Say that the target is zero. If the first access to the array is left of center, answer $-1$, and mentally set the elements to the left to be $-2,-3,\ldots$. If the first access is right of center, answer $+1$, and mentally set the elements to the right to be $2,3,\ldots$.

Suppose the first access was right of center, say position $i$, and consider the second access. If it it to the right of the first access, then you already know what to answer. Otherwise, there are two cases. If the accessed position $j$ is less than $i/2$, answer $-1$ (and fill in elements to the left). If it was more than $i/2$, answer $+1/2$ (and fill in elements to the right up to position $i$).

Continuing in this way, at each step the number of positions which could contain the target element is at most halved at each step. Finally, when only one element is still at stake, without querying it, the algorithm cannot know for sure whether the array contains the target element or not. It takes $\log_2 n$ steps to reach this step.

The foregoing actually shows that binary search is optimal for searching a sorted array.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

There are $n$ possible answers. Each comparison gives you at most one bit of information. You need at least $\lg n$ bits of information to describe the answer, so you'll need at least $\lg n$ comparisons.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.