第18课：二分查找

// 思路：对a数组中每个元素a[i]，在b数组中二分查找x-a[i]。
int a[100001];
int b[100001];
int main() {
    int n, m, x;
    cin>>n>>m>>x;
    for (int i = 0; i < n; i++) cin>>a[i];
    for (int i = 0; i < m; i++) cin>>b[i];
    for (int i = 0; i < n; i++) {   // 对每个a[i]
        int y = x - a[i];   
        int z = lower_bound(b + 0, b + m, y) - b;   // 在b中二分查找x-a[i]
        if (z < m && b[z] == y) {   // 找到x-a[i]
            cout<<i<<" "<<z;   
            return 0;
        }
    }
}

数组a（从下标1开始）：
int p = lower_bound(a+1, a+n+1, k)-a：返回数组a中大于等于k的第一个值的下标
int p = upper_bound(a+1, a+n+1, k)-a：返回数组a中大于k的第一个值的下标
注：如果没有找到，返回n+1。

字符串：
int p = lower_bound(s.begin(), s.end(), k)-s.begin()：返回字符串s中大于等于k的第一个值的下标
int p = upper_bound(s.begin(), s.end(), k)-s.begin()：返回字符串s中大于k的第一个值的下标