基于BinarySearch查找有序数组区间元素索引的问题求助

教授布置任务：在升序排列的温度数组中，使用二分查找找出给定区间内所有元素的索引，允许0.9的误差。例如区间[20,25]中，19.1、25.9符合要求，19、26不符合。

我的思路是先找到区间的上下边界索引，再取两者之间的所有索引，但实现的findLowerBound函数返回-1，导致程序输出从-1到上边界的错误索引，程序可运行但结果不正确。

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

核心逻辑错误 #

原代码的二分查找条件完全错误：

• 未明确符合条件的数值范围：符合要求的数值应满足 区间左端点-0.9 ≤ 数值 ≤ 区间右端点+0.9
• 用绝对差判断时未覆盖等于0.9的情况，且越界访问middle-1/middle+1会触发异常
• 二分查找的方向逻辑混乱，无法正确定位边界

修复后的代码 #

修正边界查找函数 #

// 找到第一个 >= (target - 0.9) 的元素索引
static int findLowerBound(double[] arr, double target)
{
    double lowerThreshold = target - 0.9;
    int low = 0;
    int high = arr.Length - 1;
    int result = arr.Length; // 默认返回数组长度，表示无符合条件的元素

    while (low <= high)
    {
        int middle = low + (high - low) / 2;
        if (arr[middle] >= lowerThreshold)
        {
            result = middle;
            high = middle - 1; // 向左寻找更早的符合条件的索引
        }
        else
        {
            low = middle + 1; // 当前值过小，向右查找
        }
    }
    return result;
}

// 找到最后一个 <= (target + 0.9) 的元素索引
static int findUpperBound(double[] arr, double target)
{
    double upperThreshold = target + 0.9;
    int low = 0;
    int high = arr.Length - 1;
    int result = -1; // 默认返回-1，表示无符合条件的元素

    while (low <= high)
    {
        int middle = low + (high - low) / 2;
        if (arr[middle] <= upperThreshold)
        {
            result = middle;
            low = middle + 1; // 向右寻找更晚的符合条件的索引
        }
        else
        {
            high = middle - 1; // 当前值过大，向左查找
        }
    }
    return result;
}

修正区间提取函数 #

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

    // 只有当上下边界有效时，才收集索引
    if (lowerBound <= upperBound && lowerBound < arrNumber.Length && upperBound >= 0)
    {
        // 注意是 <= upperBound，避免漏掉最后一个符合条件的元素
        for (int i = lowerBound; i <= upperBound; i++)
        {
            result.Add(i);
        }
    }

    return result.ToArray();
}

修正Main函数的越界问题 #

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

    // 避免空数组或索引越界
    if (index.Length > 0)
    {
        if (index[0] > 0)
            Console.WriteLine(arrNumber[index[0] - 1]);
        if (index[index.Length - 1] < arrNumber.Length - 1)
            Console.WriteLine(arrNumber[index[index.Length - 1] + 1]);
    }
    Console.ReadLine();
}

修复说明 #

1. 明确符合条件的数值阈值，避免用绝对差的模糊判断
2. 二分查找逻辑采用标准边界定位写法，确保正确找到第一个/最后一个符合条件的元素
3. 增加边界有效性检查，避免空数组或越界访问异常
4. 修正区间索引收集的循环条件，确保不会漏掉最后一个元素

内容的提问来源于stack exchange，提问作者Alihan Femi