Count the number of occurrences of a number in a sorted array

Question

My teacher gave me the next task:

On a sorted array, find the number of occurrences of a number.
The complexity of the algorithm must be as small as possible.

This is what I have thought of:

public static int count(int[] a, int x)
{
    int low = 0, high = a.length - 1;

    while( low <= high )
    {
        int middle = low + (high - low) / 2;

        if( a[middle] > x ) {
            // Continue searching the lower part of the array
            high = middle - 1;
        } else if( a[middle] < x ) {
            // Continue searching the upper part of the array
            low = middle + 1;
        } else {
            // We've found the array index of the value
            return x + SearchLeft(arr, x, middle) + SearchRight(arr, x, middle);
        }
    }

    return 0;
}

SearchLeft and SearchRight iterate the array, until the number doesn't show.

I'm not sure if I have achieved writing the faster code for this problem, and I would like see other opinions.

Edit: After some help from comments and answers, this is my current attempt:

public static int count(int[] array, int value)
{
    return SearchRightBound(array, value) - SearchLeftBound(array, value);
}

public static int SearchLeftBound(int[] array, int value)
{
    int low = 0, high = array.length - 1;

    while( low < high )
    {
        int middle = low + (high - low) / 2;

        if(array[middle] < value) {
            low = middle + 1;
        }
        else {
            high = middle;
        }
    }

    return low;
}

public static int SearchRightBound(int[] array, int value)
{
    int low = 0, high = array.length - 1;

    while( low < high )
    {
        int middle = low + (high - low) / 2;

        if(array[middle] > value) {
            high = middle;
        }
        else {
            low = middle + 1;
        }
    }

    return low;
}

Answer 1

SearchLeft and SearchRight iterate the array, until the number doesn't show.

That means if the entire array is filled with the target value, your algorithm is O(n).

You can make it O(log n) worst case if you binary-search for the first and for the last occurrence of x.

// search first occurrence
int low = 0, high = a.length - 1;
while(low < high) {
    int middle = low + (high-low)/2;
    if (a[middle] < x) {
        // the first occurrence must come after index middle, if any
        low = middle+1;
    } else if (a[middle] > x) {
        // the first occurrence must come before index middle if at all
        high = middle-1;
    } else {
        // found an occurrence, it may be the first or not
        high = middle;
    }
}
if (high < low || a[low] != x) {
    // that means no occurrence
    return 0;
}
// remember first occurrence
int first = low;
// search last occurrence, must be between low and a.length-1 inclusive
high = a.length - 1;
// now, we always have a[low] == x and high is the index of the last occurrence or later
while(low < high) {
    // bias middle towards high now
    int middle = low + (high+1-low)/2;
    if (a[middle] > x) {
        // the last occurrence must come before index middle
        high = middle-1;
    } else {
        // last known occurrence
        low = middle;
    }
}
// high is now index of last occurrence
return (high - first + 1);

Answer 2

Well this is essentially binary search + walking towards the boundaries of the solution interval. The only way you could possibly speed this is up is maybe cache the last values of low and high and then use binary search to find the boarders as well, but this will really only matter for very large intervals in which case it's unlikely that you jumped right into it.