我的教授有一个任务，我需要使用 BinarySearch 搜索有序数组，并找到给定间隔内所有值的索引。我目前解决该问题的方法是找到符合要求的最低值，然后获取其索引，然后获取最高值，然后获取这两者之间的所有索引。这种方法应该可行，因为数组是按升序排列的。我的问题是我无法让找到下限的函数起作用。
对于问题。我没有得到下边界，而是得到了 -1，因此算法得到了从 -1 到上边界的所有索引。我们的教授并不关心我们是否自己实现算法，只要我们能够在他面前捍卫它并理解它即可。程序运行良好，但给出了错误的结果。它没有给我包含适合该区间的所有值的实际索引，而是给我从 -1 到上限的所有索引。
我的任务是：我有一个温度数组，我需要编写一个算法，当给定一个间隔时，该算法将返回包含该间隔内的值的所有索引。误差范围是 0.9，这意味着如果我的间隔是 [20...25] 19.1 可以，但 19 不符合相同的逻辑，25.9 可以，但 21 不行。
这是我的代码：
static void Main(string[] args)
{
Random rnd = new Random();
double[] arrNumber = new double[90000000];
for (int i = 0; i < arrNumber.Length; i++)
arrNumber[i] = rnd.NextDouble() * 1000;
Array.Sort(arrNumber);
double[] interval = { 200, 250 };
var time = Stopwatch.StartNew();
int[] index = ExtractInterval(arrNumber, interval);
time.Stop();
TimeSpan timeTaken = time.Elapsed;
Console.WriteLine(timeTaken);
Console.WriteLine(index.Length);
Console.WriteLine(arrNumber[index[0] - 1]);
Console.WriteLine(arrNumber[index.Length]);
Console.ReadLine();
}
static int[] ExtractInterval(double[] arrNumber, double[] interval)
{
double start = interval[0];
double end = interval[1];
List<int> result = new List<int>();
int lowerBound = findLowerBound(arrNumber, start);
int upperBound = findUpperBound(arrNumber, end);
for (int i = lowerBound; i < upperBound; i++)
{
result.Add(i);
}
return result.ToArray();
}
static int findLowerBound(double[] arr, double lowerBound)
{
int low = 0;
int high = arr.Length - 1;
while(low <= high)
{
int middle = low + (high - low) / 2;
if(Math.Abs(arr[middle] - lowerBound) > 0.9)
{
high = middle - 1;
continue;
}
if (Math.Abs(arr[middle] - lowerBound) < 0.9)
{
if (Math.Abs(arr[middle - 1] - lowerBound) < 0.9)
{
low = middle - 1;
continue;
}
return middle;
}
}
return -1;
}
static int findUpperBound(double[] arr, double upperBound)
{
int low = 0;
int high = arr.Length - 1;
while (low <= high)
{
int middle = low + (high - low) / 2;
if (Math.Abs(arr[middle] - upperBound) > 0.9)
{
high = middle - 1;
continue;
}
else if (Math.Abs(arr[middle] - upperBound) < 0.9)
{
if (Math.Abs(arr[middle + 1] - upperBound) < 0.9)
{
low = middle + 1;
continue;
}
else
{
return middle;
}
}
}
return -1;
}
有人可以帮助我吗？
如果你可以随意使用框架方法，就不要自己实现二分查找。使用Array.BinarySearch。请注意，您可能需要阅读几次返回值的描述才能理解它：
指定值在指定数组中的索引，如果找到值；否则为负数。如果未找到 value 并且 value 小于数组中的一个或多个元素，则返回的负数是大于 value 的第一个元素的索引的按位补码。如果未找到 value 并且 value 大于数组中的所有元素，则返回的负数是（最后一个元素的索引加 1）的按位补码。如果使用未排序的数组调用此方法，则返回值可能不正确，并且可能返回负数，即使数组中存在值。
所以我们需要考虑所有情况
var lowerIndex = Array.BinarySearch(arrNumber, lowerBound)
if(lowerIndex >= 0){
// Exact match
}
else{
lowerIndex = ~lowerIndex; // ~ means "bitwise complement"
if(lowerIndex < arrNumber.Length){
// found index of value next larger than lowerBound
}
else {
// lowerBound larger than all items
}
}
上限看起来类似，但您需要减去 1 才能获得所有有效温度，并且需要检查结果索引是否仍大于零。如果存在完全匹配，您可能需要优化搜索，或使用从不将值进行相等比较的自定义比较器。从这里开始，对下限和上限执行相同的操作并构建范围应该相当简单。
如果您有容差，只需在搜索之前将其应用于边界即可。所以 [20...25] 将变成 [19.1 ... 25.9]。
我还建议使用一些足够短的数组来测试您的代码，以便您可以单步执行代码。特别注意边缘情况或错误情况：