Count the number of times a particular number appears in a sorted array of integers

Question

I had an interview question awhile back that went more or less as follows:

You have a sorted array of integers representing the ages of every person living on earth. There's a single entry in the array representing the current age (in years) of every individual. For example, if there were 100 million people of age 20, you would have 100 million 20's in a row. For example, if you had an array like:

1 1 1 1 1 2 2 2 3 3 3 3 3 3 4 4....

that would indicate that there are 5 people who are five years old, 3 people who are two years old, 6 people who are three years old, etc. What's the fastest way to determine the number of people who are in a particular age group (keeping in mind, of course, that the actual array will have around 7 billion people in it). For simplicity, we can assume that the array actually fits in memory and, again, the array's already been sorted.

I came up with a solution that was inspired by binary search trees. Basically, if you know the index of the first and last instance of a number you can subtract to find out the number of integers. For example, in our original array:

1 1 1 1 1 2 2 2 3 3 3 3 3 3 4 4....

the number "1" occurs between the indices 0 and 4, so there are ((4 - 0) + 1) = 5 1s in the array. In order to find the ends, you just keep cutting the array in half.

If you were even more sophisticated about it, you could use statistical information to make the initial "guesses" better. As an analogy, if you're looking for the word "butter" in the dictionary, you don't actually start in the middle - since it starts with "b" you know it'll be close to the beginning, so for your initial guess it'll be close to the front, so you could save a few steps. I don't think that that would actually impact the computational complexity though. I didn't actually work through the details of that though.

My implementation's pretty ugly "as is," so I'm sure that there'll be plenty of opportunities for improvement as that goes.

I'm particularly curious, though, about what people think about the algorithm itself. Is this a reasonable solution to the problem?

Also, am I correct in saying that this is (at least approximately) O(log n) in both the best and average case? (If so, that would likely be adequate performance for the application since log2(7 billion) is approximately 32.7).

Here's the code:

/// <summary>
    /// Count the number of times a particular number occurs in a sorted integer array
    /// </summary>
    /// <param name="number">Number we want to count</param>
    /// <param name="array">Sorted array</param>
    /// <returns>The number of instances of <paramref name="number"/> in <paramref name="array"/></returns>
    private static int CountInstanceOfANumber(int number, int[] array)
    {
        int upperBound = array.Length / 2;
        int lowerBound = array.Length / 2;

        // If we "guessed" too low
        while (array[upperBound] < number)
        {
            upperBound += ((array.Length - upperBound) / 2);
        }

        // If we "guessed" too high
        while (array[upperBound] > number)
        {
            upperBound /= 2;
        }

        // Find the actual end
        while (array[upperBound] <= number)
        {
            upperBound++;

            if (upperBound == array.Length)
            {
                break;
            }
        }
        upperBound--;
        // At this point, this should contain the upper bound

        // If we guessed too "high"
        while (array[lowerBound] > number)
        {
            lowerBound /= 2;
        }

        // If we guessed too "low"
        while (array[lowerBound] < number)
        {
            if (lowerBound == 0)
                lowerBound++;
            else
            {
                lowerBound *= 2;
                if (lowerBound >= array.Length)
                {
                    lowerBound = array.Length - 1;
                    break;
                }
            }
        }

        // Find the actual value
        while (array[lowerBound] >= number)
        {
            lowerBound--;

            if (lowerBound == -1)
                break;
        }
        lowerBound++;

        // Now do arithmetic to find the actual result
        return upperBound - lowerBound + 1;
    }

And here's the code I used to test it:

        for (int x = 0; x < 100; x++)
        {
            List<int> ct = new List<int>();
            Random random = new Random();

            for (int i = 1; i <= 10; i++)
            {
                for (int j = 0; j < random.Next(1, 35); j++)
                {
                    ct.Add(i);
                }
            }

            int lookingFor = random.Next(1, 11);
            int num = CountInstanceOfANumber(lookingFor, ct.ToArray());
            int bruteForce = BruteForce(lookingFor, ct.ToArray());

            Console.WriteLine(num == bruteForce);
        }

The BruteForce method is as follows:

// A dumb brute force method that I know works
// This serves no other purpose than to be an "answer key"
private static int BruteForce(int number, int[] array)
    {
        int count = 0;

        foreach (int curr in array)
        {
            if (curr == number)
                count++;
        }

        return count;
    }

Answer 1

My gut feel is this is too much

while (array[upperBound] > number)
{
    upperBound /= 2;
}

Could go from 1/2 to 3/4 then back to 3/8
You could go back below number

This is certainly not O(log n)

while (array[upperBound] <= number)
{
    upperBound++;

Not really up to code review standards but I tested and this in O(log n)
Actually 2*(O(log n) + 1)

public static int? SimpleBinaryRange(int[] array, int target)
{   //sorted array find lenght of target
    if (array == null || array.Length == 0)
        return null;
    //Array.Sort(array);  //it sould be sorted 
    int arrayLength = array.Length;
    if (target < array[0] || target > array[arrayLength - 1])
        return null;
    //Debug.WriteLine("target {0}  array {1} ", target, string.Join(",", array));
    int left = 0;
    int right = array.Length - 1;
    int count = 0;
    int? upperRange = null;
    int lower = 0;
    // look for upper
    while (left <= right)
    {
        count++;
        int middle = left + (right - left) / 2;
        if (array[middle] > target)
        {
            right = middle - 1;
        }
        else if (array[middle] < target)
        {
            left = middle + 1;
            lower = left;
        }
        else if (middle < arrayLength - 1 && array[middle + 1] == target)
        {
            // this is where you abort and go O(n)
            left = middle + 1;  // looking for the last
        }
        else
        {
            upperRange = middle;
            break;
        }
    }
    if(upperRange == null)
        return null;
    left = lower;
    //right can leave alone
    // look for lower
    while (left <= right)
    {
        count++;
        int middle = left + (right - left) / 2;
        if (array[middle] > target)
        {
            right = middle - 1;
            lower = right;
        }
        else if (array[middle] < target)
        {
            left = middle + 1;
        }
        else if (middle > 0 && array[middle - 1] == target)
            right = middle - 1;  
        else
        {
            lower = middle;
            break;
        }
    }
    int rangeCount = (int)upperRange - lower + 1;
    count = 0;
    foreach (int i in array)
    {
        if (i == target)
            count++;
        else if (i > target)
            break;
    }
    if (count != rangeCount)
        Debug.WriteLine("count != rangeCount");
    return rangeCount;
}