Copyright by

引入

现在给出一个有序数组

和一个数x

求x在本数组的哪个位置第一次出现

法一：首先想到枚举，找到就输出

但是sei还这么做啊~

法二：借用二分答案的思路，二分第一次可能出现的区间即可

那么来一份可爱的代码吧~

#include<bits/stdc++.h>

using namespace std;

#define AwA 100010

int n;
int a[AwA];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int qwq;
    cin >> qwq;

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] < qwq) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    cout << l << " " << a[l] << endl;

    return 0;
}

通过输入我们可以发现

这份代码会返回的是第一个大于等于x的位置

同样，在原代码的基础上稍作修改可以返回第一个大于x的位置

#include<bits/stdc++.h>

using namespace std;

#define AwA 100010

int n;
int a[AwA];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int x;
    cin >> x;

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] <= x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    cout << l << " " << a[l] << endl;

    return 0;
}

你说得对，但是……

我们还有法三：

有能力的同学要掌握的啊（bushi)

有个神奇的叫stl的东东，帮我们提前写好了上面两种算法：

直接拿来用就完事力（喜）

#include<bits/stdc++.h>

using namespace std;

#define AwA 100010

int n;
int a[AwA];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int x;
    cin >> x;

    //lower_bound函数 返回第一个>=x的位置 如果没找到就会返回n+1
    int x1 = lower_bound(a + 1, a + n + 1, x) - a;
    cout << x1 << " " << a[x1] << endl;

    //upper_bound函数 返回第一个>x的位置 如果没找到就会返回n+1
    int x2 = upper_bound(a + 1, a + n + 1, x) - a;
    cout << x2 << " " << a[x2] << endl;

    //最后一个<x的位置
    int x3 = x1 - 1;
    cout << x3 << " " << a[x3] << endl;

    //最后一个<=x的位置
    int x4 = x2 - 1;
    cout << x4 << " " << a[x4] << endl;

    return 0;
}

~看起来像不像昨天某个哥哥讲的sort函数~

模板题

那么我们就可以来做题啦！

例2

1244 和为给定数

#include<bits/stdc++.h>

using namespace std;

int n, m;
int a[100010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;

    //注意数组一定是有序的才能二分
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) {
        int l = 1, r = n + 1;
        int t = m - a[i];
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= t) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l != n + 1 && a[l] == t && l != i) {
            cout << a[i] << " " << a[l] << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

或者

#include<bits/stdc++.h>

using namespace std;

int n, m;
int a[100010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;

    //注意数组一定是有序的才能二分
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) {
        int t = m - a[i];
        int l = lower_bound(a + 1, a + n + 1, t) - a;
        if (l != n + 1 && a[l] == t && l != i) {
            cout << a[i] << " " << a[l] << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

例3

1240 查找最接近元素

#include<bits/stdc++.h>

using namespace std;

int n, m;
int a[100010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;

    while (m--) {
        int t;
        cin >> t;

        int l = lower_bound(a + 1, a + n + 1, t) - a;

        if (l == n + 1) {
            cout << a[n] << endl;
        } else if (l == 1) {
            cout << a[1] << endl;
        } else {
            if (a[l] - t < t - a[l - 1]) {
                cout << a[l] << endl;
            } else {
                cout << a[l - 1] << endl;
            }
        }
    }

    return 0;
}

那么

完结撒花~awa

课后习题！！！

因为一本通没有剩下的二分查找的题了

所以这里从洛谷搞了几道

P2249 查找

P1102 数对

P1678 烦恼的高考志愿