二分

• 本质：不同性质的边界

一、整数

1. 步骤
2. 找中间值：
   1. mid = (l + r) >> 1
   2. mid = (l + r + 1) >> 1
3. 三个要点
4. 判断mid在哪一边，是否包含在内
5. mid怎么取
   1. 两种
      1. mid = (l + r) >> 1（向下取整）
         1. (l, mid) (mid + 1, r)
      2. mid = (l + r + 1) >> 1（向下、上取整）
         1. (l, mid - 1) (mid, r)

//789 sh
#include <iostream>
using namespace std;

const int N = 100000;
int arr[N];

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    int num, l, r;
    for (int i = 0; i < q; i++)
    {
        scanf("%d", &num);
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (arr[mid] >= num)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if (arr[l] != num)         //即没有找到
        {
            cout << "-1 -1" << endl;
        }
        else
        {
            cout << l << " ";##

            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (arr[mid] <= num)
                {
                    l = mid;
                }
                else
                {
                    r = mid - 1;
                }
            }
            cout << l << endl;
        }
    }
    return 0;
}

二、浮点数

//790 数的三次方根
#include <iostream>
using namespace std;
int main(){
    double l = -10000, r = 10000;
    double n;
    cin >> n;
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid * mid * mid < n){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    printf("%lf", l);
    return 0;
}