Count the number of appearances of a value in a sorted array in O(log n) complexity

Question

How can I build a function that returns the number of appearances of a given int x in a sorted array, in O(log n) complexity?

static public int count (int [] a, int x);

I'm thinking I might use a binary search to the find the first / last appearance, then continue searching for the last / first appearance, and return the number of instances, but that this is O(log n) complexity .

Answer 1

Your idea actually works in time O(log n) if you implement it correctly. Do one binary search to find the index i of the first copy of the element, then do another binary search to find the index j of the last copy of the element, then return j - i + 1. Each binary search takes time O(log n), so the total work done is O(log n) + O(log n) = O(log n).