How to find the number of occurences of a number in a sorted Array in O(logn)

Question

I have a sorted Array of Integers. Given a number, how to find the number of occurences of that number in O(logn) even the worst case.

Answer 1

Binary search for the number, then binary search for the start and the end of the run.

Answer 2

Do one binary search for the point where all elements to the left are smaller than your number and all to the right are equal or greater and one for the point where all elements are smaller or equal to the left and greater to the right.

In other words: in one search your "test" is <, while in the other search the test is <=.

Both searches are log n, so that's your total.

For example, in C++ the two functions you'd need are std::lower_bound and std::upper_bound - it seems like the existing Java binary search functions (on Collections) always try to look for a specific value, so you probably have to implement the search yourself if you're using that.

It's important that you use a binary search variant that uses only a binary predicate! If you use a variant that checks whether it hit a specific key "by accident" will sometimes terminate too soon for this specific task.

Answer 3

Search for the insertion points of number + 0.5 and number - 0.5 using two binary searches. The number of elements with value number in the list is the difference of the positions (indices) of these two insertion points.

Answer 4

Run the function below once as it is and once with the if condition changed to if(a[mid]<=val) and the corresponding changes in the recursive calls. The two values returned are the starting and ending occurence of the particular value.

      int  binmin(int a[], int start, int end,int val )
        {
         if(start<end)
            {
            int mid = (start+end)/2;
            if(a[mid]>=val)
            {
                binmin(a,start,mid-1,val);
            }
            else if(a[mid]<val)
            {
                binmin(a,mid+1,end,val);
            }

    }
    else if(start>end)
            return start;



  }