Given a sorted array of integers and a target integer, let’s say we want to find the number of occurrences of the target integer.

It is well-known that a binary search can give 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 give time complexity less than $ P(\lg n)?$ Otherwise, is there a proof to prove that $ O(\lg n)$ is the theoretical lower bound?