二分，find（）函数用法（找数对例题）

lower_bound()

返回值是第一个大于等于 target 的值的地址，用这个地址减去first，得到的就是第一个大于等于target的值的下标。

在数组中：

int n = lower_bound(a , a + x , target) - a;//x 为数组的长度

在vector容器中：

int n = lower_bound(a.begin() , a.end(),target) - a.begin();

upper_bound（）

用于在有序序列中查找第一个大于某个值的元素的位置。

find（）

(C++) 常用STL容器查找函数find()使用小结_set容器find函数-CSDN博客

在C++中，可以使用STL容器的find()函数来在数组中查找特定的数字。find()函数返回一个迭代器，指向第一个匹配的元素，如果没有找到匹配的元素，则返回指向容器末尾的迭代器。

以下是一个使用find()函数在数组中查找数字的示例：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};

    // 使用find()函数查找数字3
    auto it = std::find(nums.begin(), nums.end(), 3);

    if (it != nums.end()) {
        std::cout << "数字3在数组中的位置是：" << std::distance(nums.begin(), it) << std::endl;
    } else {
        std::cout << "数字3未找到" << std::endl;
    }

    return 0;
}

输出结果为：

数字3在数组中的位置是：2

如果要查找的数字不存在于数组中，find()函数将返回指向容器末尾的迭代器，可以通过与容器的end()迭代器进行比较来判断是否找到了匹配的元素

一道例题

P1102 A-B 数对

题目描述

给出一串正整数数列以及一个正整数?C，要求计算出所有满足A?B=C?的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 N,C。

第二行，N?个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 A?B=C?的数对的个数。

输入输出样例

输入 #1复制

4 1
1 1 2 3

输出 #1复制

3

说明/提示

对于?75%75%?的数据，1≤N≤2000。

对于?100%100%?的数据，1≤N≤2×105，0≤ai?<230，1≤C<230。

2017/4/29 新添数据两组

#include<bits/stdc++.h>
using namespace std;
long a[200001];
long N,C,ans;
int main()
{
    cin>>N>>C;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+N+1);
    for(int i=1;i<=N;i++)
    {
    	int x=upper_bound(a+1,a+N+1,a[i]+C)-a;
    	int y=lower_bound(a+1,a+N+1,a[i]+C)-a;
    	//cout<<x<<" "<<y<<endl;
        ans+=(x-y);
    }
    cout<<ans;
    return 0;
}
 

看看中间的过程