algorithm - 检查一个数字是否存在于给定的一组范围内

Question

假设我们有一组 N 个范围，(A1, B1) (A2, B2) (A3, B3) ... (An, Bn)，其中 Ai 表示 a 的起点，Bi 表示 a 的终点范围。 (Ai、Bi为正整数)

我们如何使用二分查找来检查给定的整数(例如 X)是否至少存在于 N 个范围之一中？

我的方法:

1. 首先按 x 坐标排序范围，然后按 y 坐标排序。

2. 找到大于或等于 X 的最小 x 坐标。

3. 检查是否满足该范围。

4. 如果是，我们有解决方案。

现在，如果该范围不包含 X，我的下一步应该是什么？

或者，解决方案应该完全不同吗？

Answer 1

我从你的问题描述中得到的是，你有像(a1,b1)，(a2,b2)这样的对。其中，ax 是范围的开始，bx 是结束。现在您得到一个数字n，您想要搜索该数字是否在任何范围内。
首先排序，然后合并重叠范围，然后应用二分搜索:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector < pair <int , int> > b;
    b.push_back(make_pair(5,10));
    b.push_back(make_pair(75,100));
    b.push_back(make_pair(33,67));
    b.push_back(make_pair(9,21));
    b.push_back(make_pair(28,67));
    int m = b.size();
    sort(b.begin(), b.end());
    int j = 0;
    for (int i = 1; i < m; i++) {
        if (b[i].first <= b[j].second) {
            if (b[i].second > b[j].second) {
                b[j].second = b[i].second;
            }
        } 
        else {
            j++;
            b[j] = b[i];
        }
    }
    m = j + 1;
    for(int i = 0; i< m;i ++) {
        cout << b[i].first << " " << b[i].second << endl;
    }
    // Apply binary search now
    return 0;
}

希望这能解决您的问题。我把二分查找部分留给了你作为练习。