我的教授有一个任务,我需要使用 BinarySearch 搜索有序数组,并找到给定间隔内所有值的索引。我目前解决该问题的方法是找到符合要求的最低值,然后获取其索引,然后获取最高值,然后获取这两者之间的所有索引。这种方法应该可行,因为数组是按升序排列的。我的问题是我无法让找到下限的函数起作用。
对于问题。我没有得到下边界,而是得到了 -1,因此算法得到了从 -1 到上边界的所有索引。我们的教授并不关心我们是否自己实现算法,只要我们能够在他面前捍卫它并理解它即可。程序运行良好,但给出了错误的结果。它没有给我包含适合该区间的所有值的实际索引,而是给我从 -1 到上限的所有索引。
我的任务是:我有一个温度数组,我需要编写一个算法,当给定一个间隔时,该算法将返回包含该间隔内的值的所有索引。误差范围是 0.9,这意味着如果我的间隔是 [20...25] 19.1 可以,但 19 不符合相同的逻辑,25.9 可以,但 26 不行。
这是我的代码:
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 才能获得所有有效温度,并且需要检查结果索引是否仍大于零。
为了确保在多个完全匹配的情况下找到第一个/最后一个项目,您可以使用自定义比较器,这本质上保证您永远不会遇到“完全匹配”的情况,而是找到第一个或下一个较大的项目。
class LowerComparer : IComparer<double>
{
public int Compare(double x, double y) => x < y ? -1 : 1 ;
}
class UpperComparer : IComparer<double>
{
public int Compare(double x, double y) => x <= y ? -1 : 1;
}
从这里开始,对下限和上限执行相同的操作并构建范围应该相当简单。但请注意索引,在这样的代码中很容易出现逐一错误。
如果您有容差,只需在搜索之前将其应用于边界即可。所以 [20...25] 将变成 [19.1 ... 25.9]。
我还建议使用一些足够短的数组来测试您的代码,以便您可以单步执行代码。特别注意边缘情况或错误情况: