整数二分

本质：

  1. 如果有单调性的话，可以二分；但二分的题目，不一定一定要单调性；所以本质不是单调性
  2. 在一个区间内，我们定义了一个性质，这个性质左半边满足，右半边不满足，可以将区间一分为二；二分可以寻找边界

主要思想：
整数二分思路图示

  1. 以红色区域为True，找分界点（以红色的边界点为分界点）

    1. 找到中间值（mid = (l + r + 1)/2）

    2. 查看中间值性质（在左半边还是右半边）：

      a. [mid, r] mid处于左半边，所以分界点一定处于这里（mid到 r，包括mid）

      b. [l, mid - 1] mid处于右半边，所以分界点处于左半边 （因 此时 r = mid - 1所以mid需要在之前+1来保证它概括到红色右边 界：mid = (l + r + 1) / 2， 且当情况为 l = r - 1 时，l经过操作还是 l = (l + r) / 2向下取整，还是l，死循 环）

  2. 以绿色区域为True（以绿色的边界点为分界点）

    1. mid = (l + r ) / 2

    2. 查看中间值性质

      a. [l, mid], inclusive

      b. [mid + 1, r] 因mid为False，所以一定从mid + 1开始 （此时 l = mid + 1, 所以mid原本要保证在floor：mid = (l + r) / 1，这样让它能概括到右半边的左边界）

Code 题目（Acwing 789） 找到sorted数组中的数的起始和终止位置，若没有这个数，便返回-1, -1 输入：数组长度，询问个数，数组 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int q[N];

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

    while (m--)
    {
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        // 找到起始值
        while (l < r)
        {
            // 要满足的条件是左边<x，右边>=x，就是找绿色区域
            int mid = l + r >> 1;
            if (q[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        // 若第一个>=x的值不为x，即x不存在于数组
        if (q[l] != x)
            cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';
            int l = 0, r = n - 1;
            // 找终止值
            while (l < r)
            {
                // 要满足的条件是：左边<=x,右边>x，即找红色区域
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x)
                    l = mid;
                else
                    r = mid - 1;
            }
            cout << r << endl;
        }
    }
    return 0;
}

浮点数二分

主要思想和整数二分一致，但不用考虑边界问题

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = 0, r = x;
    while (r - l > 1e-6)
    {
        double mid = (l + r) / 2;

        if (mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    printf("%lf\n", r);
    return 0;
}