C# - 帮助优化循环

Question

我有一段代码，大体上如下所示。问题是我正在触发这段代码 10 次，需要对其进行更优化。欢迎提出任何建议。

//This array is in reality enormous and needs to be triggered loads of times in my code
int[] someArray = { 1, 631, 632, 800, 801, 1600, 1601, 2211, 2212, 2601, 2602 };

//I need to know where in the array a certain value is located
//806 is located between entry 801 and 1600 so I want the array ID of 801 to be returned (4).
id = 806

//Since my arrays are very large, this operation takes far too long 
for (int i = 0; i < someArrayLenght; i++)
{
  if (someArray[i] <= id)
    return i;
}

编辑:抱歉弄错了条件。当 806 大于 801 时，它应该返回 id。希望你能理解它。

Answer 1

数组值看起来是有序的。如果确实如此，请使用 binary search :

int result = Array.BinarySearch(someArray, id);
return result < 0 ? (~result - 1) : result;

如果搜索到的值没有出现在数组中，Array.BinarySearch 将返回下一个更大值索引的按位补码。这就是为什么我要测试负数并在上面的代码中使用按位补码运算符。结果应该与您的代码中的结果相同。

二分查找的运行时间是对数的，而不是线性的。也就是说，在最坏的情况下，只需要搜索 log₂ n 个条目而不是 n(其中 n 是数组的大小)。