C#中基于二分查找实现点在多区间内的判断逻辑问题求助

首先，你的二分查找失效的核心原因有两个：区间集合未保证有序，以及自定义Comparer的逻辑完全不符合二分查找的要求。二分查找的前提是集合必须按特定规则排序，且Comparer要能正确判断查找值与集合元素的相对位置，你的代码在这两点上都出了问题。

问题拆解 #

1. 区间未排序：二分查找只能在有序集合上工作，你需要确保区间列表按区间起始值升序排列，否则二分查找的指针移动逻辑会完全混乱。
2. Comparer逻辑混乱：你原来的RangeComparerPoint混淆了参数含义（比如用f2.Item2作为currPos，但这个值根本没用），而且比较逻辑无法正确告诉二分查找：当前点是在区间的左边、右边还是内部，导致多区间时跳过了第一个区间的检测。

修复步骤 #

步骤1：确保区间集合有序 #

首先，手动排序或者初始化时就按起始值升序排列你的区间列表：

var ranges = new List<Tuple<int, int>>()
{
    Tuple.Create(1, 3),
    Tuple.Create(6, 9),
    Tuple.Create(11, 15)
};
// 确保按区间起始值升序排序（如果初始化时没排序的话）
ranges.Sort((a, b) => a.Item1.CompareTo(b.Item1));

步骤2：重写正确的Comparer #

我们需要一个能正确比较「待查找的点」和「区间」的Comparer，明确参数含义：

• 第一个参数是集合中的区间（Tuple<int, int>，Item1=区间起始，Item2=区间结束）
• 第二个参数是待查找的点（用Tuple<int, int>的Item1存点的值，Item2可以随便填，比如0）

代码如下：

class RangePointComparer : IComparer<Tuple<int, int>>
{
    public int Compare(Tuple<int, int> range, Tuple<int, int> point)
    {
        int targetPos = point.Item1;
        
        // 点在区间左侧：告诉二分查找需要往左找
        if (targetPos < range.Item1)
        {
            return 1;
        }
        // 点在区间右侧：告诉二分查找需要往右找
        if (targetPos > range.Item2)
        {
            return -1;
        }
        // 点在区间内：匹配成功
        return 0;
    }
}

步骤3：正确调用二分查找 #

现在用修复后的逻辑检测点是否在区间内：

int target = 2; // 测试点，可以换成其他值比如7、12、4等
var pointTuple = Tuple.Create(target, 0); // 用Item1存点的值
var comparer = new RangePointComparer();

int resultIndex = ranges.BinarySearch(pointTuple, comparer);

if (resultIndex >= 0)
{
    Console.WriteLine($"点 {target} 落在区间 [{ranges[resultIndex].Item1}, {ranges[resultIndex].Item2}] 内");
}
else
{
    Console.WriteLine($"点 {target} 不在任何给定区间内");
}

为什么原来的代码会失效？ #

你原来的Comparer逻辑中，错误地引入了无用的currPos变量，并且比较逻辑无法正确引导二分查找的指针移动——当处理第一个区间时，你的逻辑返回了错误的结果，导致二分查找直接跳过了第一个区间，转而在后两个区间中查找，自然无法检测到第一个区间内的点。

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