1.算法思想

每一次都会把答案的搜索范围缩小一半，然后递归求解答案所在的一半子问题，直到最后只剩下一个元素，就是所要求解的问题答案
二分的本质：找到一个性质，使得问题的答案一般满足，一半不满足，二分一定可以求的边界。

2.问题特征

（1）70%的问题单调性的题目都可以二分
（2）95%的题目存在两段性的特征，要求答案可以落在两段性其中一段的边界上

3. 二分题目分析流程

step1: 确定二分的边界
step2: 编写二分模板
step3: 设计一个check函数，要求答案在性质的边界上
step4: 判断一下如何更新区间
step5: 如果更新表达式写的是 l = mid， r = mid - 1, 则计算 mid = l + r + 1 >> 1

4. 二分模板

l = xx, r = xx;
while(l < r){
    mid = l + r >> 1;
    if(check(x)) xx
    else    xx
}

if l xx

题目描述举例

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

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

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

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

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

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

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

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

1≤n≤100000
1≤q≤10000
1≤k≤10000

样例

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

二分

首先分析题目，题目关键信息
（1）升序排列的长度为n的整数数组：单调性
（2）一个元素k的起始位置和终止位置：对于一个元素k， 思考如何通过元素k把数组分成两段。由于升序，所以设计check函数 <= x 或者 >= x的性质，则可以将数组分成两段。

时间复杂度

$O(nlogn)$

C 代码

#include<stdlib.h>
#include<stdio.h>

#define MAX_LEN 100010

int a[MAX_LEN];

int main(){

    int n, q;
    scanf("%d%d", &n, &q);

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

    int k = 0;
    for(int i = 0; i < q; i++){
        scanf("%d", &k);

        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] >= k) r = mid;
            else    l = mid + 1;
        }

        if(a[l] == k){
            printf("%d ", l);
        }else{
            printf("-1 -1\n");
            continue;
        }

        l = 0, r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] <= k) l = mid;
            else    r = mid - 1;
        }
        printf("%d\n", l);
    }

    return 0;
}