二分

二段性

当给定一个条件时，两边呈现出有且仅有的两种状态。

整数二分

板子：

单调递增序列a中查找>=x的数中最小的一个(x或x的后继)

public int bsearch_1(int l,int r){
        while (l < r){
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }

单调递增序列a中查找<=x的数中最大的一个(x或x的前驱)

public int bsearch_2(int l,int r){
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (a[mid] <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }

若bsearch_2中也采用 mid = l + r >> 1

当r - l 等于1时，就有mid = l + r >> 1 = l，进入l = mid分支会造成死循环，若进入r = mid - 1分支会造成l > r，循环不能以l = r结束。

无解情况

mid = (l + r) >> 1不会取到r这个值，mid = (l + r + 1) >> 1不会取到l这个值。可以利用这个性质来处理无解情况，把最初二分区间[1，n]分别扩大为[1，n + 1]和[0，n]，把a数组的一个越界下标包含进来，如果最后二分终止于扩大后的这个越界下标上，则说明a中不存在所求的数。

实数域二分

板子：

public double bsearch_3(double l ,double r){
        double eps = 1e-6;
        while (r - l > eps){
            double mid = (l + r) / 2;
            if (check(mid)) r = mid;
            else l = mid;
        }
        return l;
    }

例题：

整数二分：

给定一个按照升序排列的长度为 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

import java.util.Scanner;

public class Demo01 {
    static int N = (int)1e5 + 10;
    static int n,m;
    static int q[] = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            q[i] = sc.nextInt();
        }
        while (m -- > 0){
            int v = sc.nextInt();

            int l = 0;
            int r = n - 1;

            while (l < r){
                int mid = l + r >> 1;
                if (q[mid] >= v) r = mid;
                else l = mid + 1;
            }

            int left = l;

            if (q[l] != v){
                System.out.println(-1 + " " + -1);
                continue;
            }

            l = 0;
            r = n;

            while (l < r){
                int mid = l + r >> 1;
                if (q[mid] > v) r = mid;
                else l = mid + 1;
            }
            System.out.println(left + " " + (l - 1));
        }
        sc.close();
    }
}

浮点数二分：

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

import java.util.Scanner;

public class Demo02 {
    static double eps = 1e-8;
    static double n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextDouble();

        double l = -10000;
        double r = 10000;

        while (r - l > eps){
            double mid = (l + r) / 2;

            if (mid * mid * mid < n) l = mid;
            else r = mid;
        }

        System.out.printf("%.6f",l);

        sc.close();
    }
}