Algorithm advice: Find count of number in sorted array

Question

The problem:

Let A = A[1]<=A[2]....A[n] be a sorted array of n numbers. Let x be a number. Design an O(log n) time algorithm to find the number of times x appears in the array. What is the time complexity.

My answer:

Using a binary search find if x = middle. If x is middle then there is a chance x could appear in left and right side of middle. So create left array L[] and right array R[]. Using binary search find the the first time x appeared in L[]. Do the same thing for R[], but to find the last time x appeared in R[]. Note the indexes. So the number of time x appeared = Lastindex - FirstIndex + 1. Time complexity 2log n + c = O(log n). It's just a 'skeleton part' of algorithm since the answer doesn't have to be elaborated. This is what I found, but is there a better solution?

Seems good (though a bit overcomplicated) to me. Note that depending on lanuage, creating the L[] and R[] array could be itself O(n) though (this can be solved by using the same array with referring to the first and last indices in each conceptual subarray) — amit
@amit Thanks for pointing out, I meant to say sub-array's. And thanks for the quick replay. — Nikii Peter
This question would benefit from a better title and better formatting to make it easier to read. — Kevin
There's a couple problem I see with your answer. 1. You talk about the case where the middle of the array is x, but you never go back to answer for if it isn't x. 2. There is no reason to create a separate left and right array, just do two binary searches on the original array and find the indexes. — Kevin

Matt Timmermans Matt Timmermans · Accepted Answer · 2016-03-25T19:26:41

Use a binary search to find the position of the first element >=x (or the end if there is no such element), and another binary search to find the position of the first element > x. The difference between these positions is the number of elements == x.

int countXs(int[] array, int len, int x)
{
    int low, high, test;
    for (low=0, high=len; low<high;)
    {
        test = low+((high-low)>>1);
        if (array[test]>=x)
            high=test;
        else
            low=test+1;
    }
    int startPos = low;
    for (low=0, high=len; low<high;)
    {
        test = low+((high-low)>>1);
        if (array[test]>x)
            high=test;
        else
            low=test+1;
    }
    int endPos = low;
    return endPos - startPos;
}

Note that low+((high-low)>>1) is floor((low+high)/2), but protected from overflows. This is ALWAYS >= low and < high, so we can safely access array[test].

Algorithm advice: Find count of number in sorted array

1 Answers