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

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?