如何提高较长数字数组的算法性能?

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(提高计算速度。