algorithm - 检查给定范围内是否存在数字

Question

假设我们有一组N个区间，(A1, B1) (A2, B2) (A3, B3) ... (An, Bn)，其中Ai表示起点，Bi表示终点范围。 (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;
}

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