【紫书】算法竞赛之二分查找笔记

一：二分查找

排序的重要意义之一就是为检索带来方便。试想一下，如果有10万个数据，要你查找某一个数，依次访问是不是有点太慢了，所以先前的大佬们就创造了二分查找这样的算法。

基本思路就是像“猜数字游戏”一样：你在心里想一个不超过1000的正整数，我可以保证在10次之内猜到它——只要你每次告诉我猜的数字比你想的大一些、小一些、或者猜中了。

小了就猜大一点的，大了就猜小一点的。

二：推荐题目——数的范围

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

三：详细题解

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 100010;
int a[N];

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 0;i < n;i++) scanf("%d", &a[i]);

    int k;
    while (q--) {
        scanf("%d", &k);

        //找左缩右
        int l = 0, r = n - 1, m;//初始化端点下标
        while (l < r) {
            m = l + r >> 1;//找到中点下标
            if (a[m] >= k) r = m;
           //中点值不小于我们的目标值，说明我们要找的在左边，所以裁剪掉右边的值。
            else l = m + 1;
            //小于右移缩短范围
        }
        if (a[l] == k) printf("%d ", l);
        else printf("-1 ");

        //找右缩左
        l = 0, r = n - 1;
        while (l < r) {
            m = l + r + 1 >> 1;
            if (a[m] <= k) l = m;
            else r = m - 1;
        }
        if (a[l] == k) printf("%d
", l);
        else printf("-1
");
    }

    return 0;
}