How do I increase the algorithm performance for lo

问题:

Thanks for looking.

Count how many numbers are less than 4 in an ordered array of numbers.

How do I increase the algorithm performance for longer array of numbers? Increase the calculation speed. Does binary search help? Outputs?

    public static int CountNumbers(int[] sortedArray, int lessThan)
    {
        int count = 0;

        for (int i = 0, len = sortedArray.Length; i < len; i++)
            if (sortedArray[i] < lessThan)
                count++;
            else return count;

        return count;
    }

Assert.AreEqual(SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4), 2);

回答1:

You should use Array.BinarySearch

static int CountNumbers(int[] sortedArray, int lessThan)
{
    if (sortedArray[0] >= lessThan) return 0;

    int lengthOfArray = sortedArray.Length;
    if (lengthOfArray == 0) return 0;
    if (sortedArray[lengthOfArray - 1] < lessThan) return lengthOfArray;

    int index = Array.BinarySearch(sortedArray, lessThan);
    if (index < 0)
        return ~index;
    // Find first occurrence in case of duplicate
    for (; index > 0 && sortedArray[index - 1] == lessThan; index--) ;
    return index;
}

回答2:

A good approach for a problem like this is to split your array in smaller parts and with the help of a ThreadPool (see https://msdn.microsoft.com/en-us/library/3dasc8as(v=vs.80).aspx) increase the calculation speed.