Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Question

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?

Answer 1

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.

Answer 2

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.