如何为更长的数组增加算法性能？

Question

谢谢你的期待。

计算有序数字数组中少于4的数字。

如何为更长的数组增加算法性能？提高计算速度。二进制搜索有帮助吗？输出？

    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);

Answer 1

你应该使用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;
}

Answer 2

对于像这样的问题，一个很好的方法是将数组拆分成较小的部分，并在ThreadPool的帮助下（参见https://msdn.microsoft.com/en-us/library/3dasc8as(v=vs.80).aspx）提高计算速度。