来源：哪吒编程

二分查找是一种在有序数组中查找某一特定元素的搜索算法。

从数组的中间元素开始搜索，如果中间元素正好是要查找的元素，则搜索过程结束；
如果小于要查找的元素，则从左半部开始继续二分查找；
如果大于要找的元素，则从右半部份开始继续二分查找。

简而言之，就是一半一半递归搜索，直至找到目标元素。

效率肯定比遍历更高。

举个最简单的例子：
有一组数字[1,3,4,6,9,12,19,20]，要找12的位置。

通过遍历：

二分查找：

效率提升明显。

看到这里，你可能还没明白，下面看一下二分查找的实际应用。

举个实际栗子：

孙悟空喜欢吃蟠桃，一天他乘守卫蟠桃园的天兵天将离开了而偷偷的来到王母娘娘的蟠桃园偷吃蟠桃。

已知蟠桃园有 N 棵蟠桃树，第 i 棵蟠桃树上有 N[i]（大于 0）个蟠桃，天兵天将将在 H（不小于蟠桃树棵数）小时后回来。

孙悟空可以决定他吃蟠桃的速度 K（单位：个/小时），每个小时他会选择一颗蟠桃树，从中吃掉 K 个蟠桃，如果这棵树上的蟠桃数小于 K，他将吃掉这棵树上所有蟠桃，然后这一小时内不再吃其余蟠桃树上的蟠桃。

孙悟空喜欢慢慢吃，但仍想在天兵天将回来前将所有蟠桃吃完。

求孙悟空可以在 H 小时内吃掉所有蟠桃的最小速度 K（K 为整数）。

1、输入

3 25 6 7 8

2、输出

7

3、说明

天兵天将8个小时后回来，孙悟空吃掉所有蟠桃的最小速度7。

第1小时全部吃完第一棵树，吃3个，
第2小时吃7个，第二棵树剩18个，
第3小时吃7个，第二棵树剩11个，
第4小时吃7个，第二棵树剩4个，
第5小时吃4个，第二棵树剩吃完，
第6小时全部吃完第三棵树，吃6个，
第7小时全部吃完第四棵树，吃7个。

题目描述有点复杂，多读几遍不难理解，意思就是：

一个小时只能在一棵桃树上吃，如果吃不完，下一个小时继续吃，如果吃完了，就不吃了，但不能去吃下一颗桃树，要守规矩。
输入几个数，表示每颗树的桃子数量；在H个小时内，以最慢的速度将这些桃子全部吃完。

很明显的回溯问题，一个一个找呗，看哪个速度最合适。

1、从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度

public class Test06 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 天兵天将将离开的时间H
        int H = arr[arr.length - 1];

        // 获取每棵数上蟠桃个数
        arr = Arrays.copyOf(arr, arr.length - 1);

        // 从少到多排序
        Arrays.sort(arr);

        // 从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度
        dfs(arr, H, 1);

        System.out.println(minSpeed);
        System.out.println("执行次数：" + num);
    }

    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 吃完所有桃子的最小速度
    static int minSpeed = 0;

    /**
     * 从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度
     */
    private static void dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }

        // 因为速度从小到大递增，当时间 <= H时，即最小速度
        if (times <= H) {
            minSpeed = K;
            return;
        } else {
            // 吃不完，加快速度
            dfs(arr, H, ++K);
        }
    }
}

假如孙猴子一小时吃100个桃子最合适，效率有点堪忧。

输入：3 25 6 7 8 输出：7 执行次数：28

2、预测一个最可能的速度

所有桃子的数量除以总时间，得出每小时吃桃子数量，我觉得这个就是比较接近最小速度的最优解。

如果吃不完，就加快速度；
如果吃完了，就吃慢一点；
哈哈

public class Test08 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 天兵天将将离开的时间H
        int H = arr[arr.length - 1];

        // 获取每棵数上蟠桃个数
        arr = Arrays.copyOf(arr, arr.length - 1);
        // 从少到多排序
        Arrays.sort(arr);

        // 预测最可能速度，优化回溯算法
        int sum = Arrays.stream(arr).sum();
        int possible = sum % H == 0 ? sum / H : sum / H + 1;

        System.out.println("预测最可能速度：" + possible);

        // 从最可能速度开始回溯，寻找H小时内吃完所有桃子的最小速度
        dfs(arr, H, possible);

        System.out.println(minSpeed);
        System.out.println("执行次数：" + num);
    }

    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 吃完所有桃子的最小速度
    static int minSpeed = 0;
    // 上一次吃完所有桃子的速度
    static int preSpeed = 0;

    private static void dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }

        // 吃不完，加快速度
        if (times > H) {
            // 如果上次已经吃完，则上次吃完的速度即最小速度
            if (preSpeed != 0) {
                minSpeed = preSpeed;
                return;
            }
            dfs(arr, H, ++K);
        } else if (times < H) {// 吃完了，再吃慢一点
            preSpeed = K;
            dfs(arr, H, --K);
        } else {// 刚好吃完，返回最小速度
            minSpeed = K;
            return;
        }
    }
}

输入：3 25 6 7 8 输出：7 预测最可能速度：6 执行次数：12

3、一切都靠猜 + 回溯，有点太小儿科了，通过二分查找正统一下

public class Test09 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 天兵天将将离开的时间H
        int H = arr[arr.length - 1];

        // 获取每棵数上蟠桃个数
        arr = Arrays.copyOf(arr, arr.length - 1);
        // 从少到多排序
        Arrays.sort(arr);

        int left = 1;
        int right = arr[arr.length - 1];
        while (left < right) {
            int mid = (left + right) / 2;
            // 吃完了，还能慢一点
            if (dfs(arr, H, mid)) {
                right = mid;
            } else {// 没吃完，吃快一点
                left = mid + 1;
            }
        }
        System.out.println(left);
        System.out.println("执行次数：" + num);
    }

    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 上一次吃完所有桃子的速度
    static int preSpeed = 0;

    private static boolean dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }
        return times <= H;
    }
}

输入：3 25 6 7 8 输出：7 执行次数：16

通过对比，还是预测一个最可能的速度效率最高，嘿嘿~