【算法】二分三步走
据查，医书有服用响豆的方法，响豆就是槐树果实在夜里爆响的，这种豆一棵树上只有一个，辨认不出来。取这种豆的方法是，在槐树刚开花时，就用丝网罩在树上，以防鸟雀啄食。结果成熟后，缝制许多布囊贮存豆荚。夜里用来当枕头，没有听到声音，便扔掉。就这么轮着枕，肯定有一个囊里有爆响声。然后把这一囊的豆类又分成几个小囊装好，夜里再枕着听。听到响声再一分为二，装进囊中枕着听。这么分下去到最后只剩下两颗，再分开枕听，就找到响豆了。
二分查找
十个二分九个错，该算法被形容 “思路很简单，细节是魔鬼”。第一个二分查找算法于 1946 年出现，然而第一个完全正确的二分查找算法实现直到 1962 年才出现。下面的二分查找，其实是二分查找里最简单的一个模板，在后面的文章系列里，我将逐步为大家讲解二分查找的其他变形形式。
适用场景
注意，绝大部分「在递增递减区间中搜索目标值」的问题，都可以转化为二分查找问题。
即 适用于在有序集合中搜索特定值
关键词：有序
基本概念
二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。一般二分查找由以下几个术语构成：
-
目标 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版本，比较正派的代码，没有用一些缩写形式）
注意：循环条件
while (low <= high)与快速排序while (low < high)的不同的，
因为我们的二分法需要查找元素是否满足条件，当 low == high 时，我们也需要判断元素是否满足条件，不满足条件依旧不能返回；
而快速排序就不一样了，我们仅仅是需要划分数组，将数组分为一小一大两部分，当 low == high 时，我们不需要判断是否满足条件了，直接划分即可。
//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;
}注意：上面的代码，mid 使用
low + (high - low) / 2的目的，是防止high + low溢出内存。如果不溢出的话，其实是和(high + low) / 2一样的效果。
为什么说是一般实现？
-
根据边界的不同（开闭区间调整），有时需要弹性调整low与high的值，以及循环的终止条件。
-
根据元素是否有重复值，以及是否需要找到重复值区间，有时需要对原算法进行改进。
那上面我们说了，一般二分查找的过程分为：预处理 – 二分查找 – 后处理，上面的代码，就没有后处理的过程，因为在每一步中，你都检查了元素，如果到达末尾，也已经知道没有找到元素。
总结一下一般实现的几个条件：
-
初始条件：
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 如何处理？
处理好了上面的问题，自然就可以顺利解决问题。
一点建议
我拉出来讲这道题的原因，绝对不是说你会了，知道怎么样做了就可以了。我是希望通过本题，各位去深度思考二分法中几个元素的建立过程，比如 Left 和 Right 我们应该如何去设置，如本题中 Right 既可以设置为 x 也可以设置为 x/2；又比如 mid 值该如何计算。大家一定要明确 mid 的真正含义有两层，第一：大部分题目最后的 mid 值就是我们要找的目标值 第二：我们通过 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
答案
做题思路：
-
我们需要一个方法来判断速度为k时能否在h小时内吃完堆
-
由于我们不能判断k的大小，那就一个一个递增去试试，去找到一个合适的值；（满足了我们二分法的适用场景）
-
然后我们想到，如果是递增有序的话，我们可以直接用二分法查找
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…,
由于返回类型是整数，小数部分将被舍去。
答案
-
这里我们很容易就想到暴力破解，从 0 开始递增一个一个看是不是满足 res * res == x，直到查找到一个数满足我们的条件
-
既然是递增有序的，我们使用二分法来分解查找
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 是第一个错误的版本。
答案
这个题目还是相当简单的….我拿出来讲的原因，是因为我的开发生涯中，真的遇到过这样一件事。当时我们做一套算薪系统，算薪系统主要复杂在业务上，尤其是销售的薪资，设计到数百个变量，并且还需要考虑异动（比如说销售A是团队经理，但是下调到B团队成为一名普通销售，然后就需要根据A异动的时间，来切分他的业绩组成。同时，最恶心的是，普通销售会影响到其团队经理的薪资，团队经理又会影响到营业部经理的薪资，一直到最上层，影响到整个大区经理的薪资构成）要知道，当时我司的销售有近万名，每个月异动的人就有好几千，这是非常非常复杂的。然后我们遇到的问题，就是同一个月，有几十个团队找上来，说当月薪资计算不正确（放在个人来讲，有时候差个几十块，别人也是会来找的）最后，在一阵漫无目的的排查之后，我们采用二分的思想，通过切变量，最终切到错误的异动逻辑上，进行了修正。
回到本题，我们当然可以一个版本一个版本的进行遍历，直到找到最终的错误版本。但是如果是这样，还讲毛线呢。。。
//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;
}
}
