【算法】二分三步走

二分查找

适用场景

注意，绝大部分「在递增递减区间中搜索目标值」的问题，都可以转化为二分查找问题。

即 适用于在有序集合中搜索特定值

关键词：有序

基本概念

二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。一般二分查找由以下几个术语构成：

• 目标 Target —— 你要查找的值

• 索引 Index —— 你要查找的当前位置

• 左、右指示符 Left，Right —— 我们用来维持查找空间的指标

• 中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引

在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。我们也称之为查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。

举例说明：比如你需要找1-100中的一个数字，你的目标是用最少的次数猜到这个数字。你每次猜测后，我会说大了或者小了。而你只需要每次猜测中间的数字，就可以将余下的数字排除一半。

不管我心里想的数字如何，你在7次之内都能猜到，这就是一个典型的二分查找。每次筛选掉一半数据，所以我们也称之为 折半查找。一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步。

当然，一般题目不太可能给你一个如此现成的题型，让你上手就可以使用二分，所以我们需要思考，如何来构造一个成功的二分查找。大部分的二分查找，基本都由以下三步组成：

• 预处理过程（大部分场景就是对未排序的集合进行排序）

• 二分查找过程（找到合适的循环条件，每一次将查找空间一分为二）

• 后处理过程（在剩余的空间中，找到合适的目标值）

二分三步走

一般参考条件：
总结一下一般实现的几个条件：

• 初始条件：left = 0, right = length - 1

• 循环条件：left <= right

• 终止：left > right

• 向左查找：right = mid - 1

• 向右查找：left = mid + 1

1. 明确左右边界

1.明确左右边界：一般左边界是数组的起始下标 left = 0，右边界的数组的结束下标 right = nums.length - 1

2. 确立中间索引

2.确立中间索引：一般是正中间向下取整，即 mid = (left + right) / 2，不过为了防止 left + right 溢出内存，我们一般采用 mid = left + (right - left) / 2 是一样的效果噢，只不过 right - left 肯定不会溢出内存。

3. 完成二分划分

3.完成二分划分：
向左查找：right = mid - 1；
向右查找：left = mid + 1

实现方式

一般实现

了解了二分查找的过程，我们对二分查找进行一般实现（这里给出一个Java版本，比较正派的代码，没有用一些缩写形式）

//JAVA
public int binarySearch(int[] array, int des) {
    int low = 0, high = array.length - 1;
    while (low <= high) {  // 与快速排序的low < high区分开来
        int mid = low + (high - low) / 2;  // 防止 high + low 溢出内存
        if (des == array[mid]) {
            return mid;
        } else if (des < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

为什么说是一般实现？

1. 根据边界的不同（开闭区间调整），有时需要弹性调整low与high的值，以及循环的终止条件。

2. 根据元素是否有重复值，以及是否需要找到重复值区间，有时需要对原算法进行改进。

那上面我们说了，一般二分查找的过程分为：预处理 - 二分查找 - 后处理，上面的代码，就没有后处理的过程，因为在每一步中，你都检查了元素，如果到达末尾，也已经知道没有找到元素。

总结一下一般实现的几个条件：

• 初始条件：left = 0, right = length - 1

• 循环条件：left <= right

• 终止：left > right

• 向左查找：right = mid - 1

• 向右查找：left = mid + 1

请大家记住这个模板原形，在后面的系列中，我们将介绍二分查找其他的模板类型。

延伸实现

记录满足条件的元素

特殊一点：满足条件就记录一次，直到最后一次，就是我们满足条件的最后答案

//JAVA
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        int res = n;  // 用来记录满足条件的答案
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (isBadVersion(mid)) {
                // 满足条件就记录覆盖一次，直到最后一次，就是我们满足条件的最后答案
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}

---

数组中必定存在满足条件的元素时的优化

可以使用此优化的情况：如果我们不需要判断最终 left == right 时是否满足条件

• 可以确定如果最后找到元素就一定满足条件

• 只需要找到最接近的元素

• 我们确定满足条件的元素一定在数组中

如果我们不需要判断最终 left == right 时是否满足条件，可以确定如果最后找到元素就一定满足条件，或者只需要找到最接近的元素，或者我们确定满足条件的元素一定在数组中，我们就可以优化为以下代码，不需要判断最后 left == right 时是否满足条件：

//JAVA
public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {  // 我们不需要审查 left == right 时的场景，因为满足条件的元素必然在数组中，所以我们也不需要记录满足条件的元素结果答案
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

递归实现

递归实现：这里二分法的递归，其实可以叫做分治法

// 明确分解策略：大问题=从n个元素中找到最大的数字并返回，折半分解，小问题=从2个元素比较大小找到最大数字并返回。
int f(int[] nums, int l, int r) {

      // 寻找最小问题：最小问题即是只有一个元素的时候
      if (l >= r) {
            return nums[l];
      }

      // 使用分解策略
      int lMax = f(nums, l, (l+r)/2);
      int rMax = f(nums, (l+r)/2+1, r);

      // 解决次小问题：比较两个元素得到最大的数字
      return lMax > rMax ? lMax : rMax;
}

思考问题

注意，绝大部分「在递增递减区间中搜索目标值」 的问题，都可以转化为二分查找问题。并且，二分查找的题目，基本逃不出三种：找特定值，找大于特定值的元素（上界），找小于特定值的元素（下界）。

而根据这三种，代码又最终会转化为以下这些问题：

• low、high 要初始化为 0、n-1 还是 0、n 又或者 1，n？

• 循环的判定条件是 low < high 还是 low <= high？

• if 的判定条件应该怎么写？

• if 条件正确时，应该移动哪边的边界？

• 更新 low 和 high 时，mid 如何处理？

处理好了上面的问题，自然就可以顺利解决问题。

一点建议

那么问题来了，如何可以彻底掌握二分法？初期我并不建议大家直接去套模板，这样意义不是很大，因为套模板很容易边界值出现错误（当然，也可能我的理解还不够深入，网上有很多建议是去直接套模板的）我的建议是：去思考二分法的本质，了解其通过收敛来找到目标的内涵，对每一个二分的题目都进行深度剖析，多分析别人的答案。你得知道，每一个答案，背后都是对方的思考过程。从这些过程中抽茧剥丝，最终留下的，才是二分的精髓。也只有到这一刻，我认为才可以真正的说一句掌握了二分。毕竟模板的目的，也是让大家去思考模板背后的东西，而不是模板本身。

实例

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23

答案

做题思路：

1. 我们需要一个方法来判断速度为k时能否在h小时内吃完堆

2. 由于我们不能判断k的大小，那就一个一个递增去试试，去找到一个合适的值；（满足了我们二分法的适用场景）

3. 然后我们想到，如果是递增有序的话，我们可以直接用二分法查找

class Solution {
    public int minEatingSpeed(int[] piles, int h) {

        // 1. 我们需要一个方法来判断速度为k时能否在h小时内吃完堆

        // 2. 由于我们不能判断k的大小，那就一个一个递增去试试，如果是递增有序的话，我们可以直接用二分法查找

        // 这是第一版左右界限，我们可以优化一下
        // int left = 1;
        // int right = Integer.MAX_VALUE;  // 这里得用最大的数，因为测试示例很大

        // 第二版左右界限，右界限我们可以取 香蕉个数的最大值max

        int left = 1;
        int right = 0;
        for (int i = 0 ; i < piles.length; i++) {
            right = piles[i] > right? piles[i] : right;
        }



        int index = 0;  // 用来记录可以吃完的速度，满足条件就记录一次，直到最后一次，就是我们的答案

        while (left <= right) {

            // 1. 如果可以吃完，那就向左边找找

            // 2. 如果不能，那就右边
            // int mid = (left + right) / 2; // 使用这个有可能导致 left + right 溢出
            int mid = left + (right - left) / 2;


            if (f(piles, mid, h)) {
                index = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return index;

    }

    // 1. 我们需要一个方法来判断速度为k时能否在h小时内吃完堆
    public boolean f(int[] piles, int k, int h) {
        int time = 0;

        for (int i = 0; i < piles.length; i++) {

            // 我的向上取整方法：
            // 1. 如果能整除，那就直接除法算时间
            // 2. 如果不能整除，那就先除法再+1
            // if (piles[i] % k == 0) {
            //     time += piles[i] / k;
            // } else {
            //     time += piles[i] / k + 1;
            // }


            // 别人的向上取整方法：
            // 可以看到，其实就是加了一个 k - 1，再除以 k，也就是说加了一个大于 0.5，小于 1 的数，向上取整
            time += (piles[i] + k - 1) / k;

        }

        return h >= time;
    }
}

69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
  由于返回类型是整数，小数部分将被舍去。

答案

1. 这里我们很容易就想到暴力破解，从 0 开始递增一个一个看是不是满足 res * res == x，直到查找到一个数满足我们的条件

2. 既然是递增有序的，我们使用二分法来分解查找

class Solution {
    public int mySqrt(int x) {

        // 如果不能使用平方根函数的话，那就只有使用 res * res == x 来计算了，我们最简单可以使用暴力破解来寻找res（即 一个一个找）

        // for (int i = 1; i <= x / 2; i++) {
        //     if ((i * i < x && (i + 1) * (i + 1) > x) || i * i == x) {
        //         return i;
        //     }
        // }

        // return x;

        // 遗憾的是，暴力破解在验证2147483647的时候超时了，只能换一个查找方法了
        // 平方根的整数部分必然 ans * ans <= x，所以满足此条件的ans都有可能是我们需要的
        int l = 0;
        int r = x;
        int ans = -1;   // 用来存储我们满足条件的答案，每次满足条件都存储一次，直到最后一次。
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;

    }
}

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。 

答案

回到本题，我们当然可以一个版本一个版本的进行遍历，直到找到最终的错误版本。但是如果是这样，还讲毛线呢。。。

//JAVA
public int firstBadVersion(int n) {
    for (int i = 1; i < n; i++) {
        if (isBadVersion(i)) {
            return i;
        }
    }
    return n;
}

我们自然是采用二分的思想，来进行查找。举个例子，比如我们版本号对应如下：

如果中间的mid如果是错误版本，那我们就知道 mid 右侧都不可能是第一个错误的版本。那我们就令 right = mid，把下一次搜索空间变成[left, mid]，然后自然我们很顺利查找到目标。

根据分析，代码如下：

//JAVA
public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

额外补充：请大家习惯这种返回left的写法，保持代码简洁的同时，也简化了思考过程，何乐而不为呢。

当然，代码也可以写成下面这个样子（是不是感觉差点意思？）

//JAVA
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        int res = n;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (isBadVersion(mid)) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

遍历答案

class Solution {
    public int search(int[] nums, int target) {

        // 顺序遍历
        int num = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == target) {
                num++;
            } else if (nums[i] > target) {
                break;
            }
        }
        return num;
    }
}

二分法答案

// 可以试试二分法
class Solution {
    public int search(int[] nums, int target) {
        // 分别二分查找 targettarget 和 target - 1target−1 的右边界，将两结果相减并返回即可。
        return helper(nums, target) - helper(nums, target - 1);
    }
    // helper() 函数旨在查找数字 tartar 在数组 numsnums 中的 插入点 ，且若数组中存在值相同的元素，则插入到这些元素的右边。
    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}