Theoretical lower bound of finding number of occurrences of a target integer in a sorted array
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.