算法学习宝典_4_二分法
来自一篇好文 ： https://www.cnblogs.com/kyoner/p/11080078.html
我周围的人几乎都认为二分查找很简单，但事实真的如此吗？二分查找真的很简单吗？并不简单。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...
这句话可以这样理解：思路很简单，细节是魔鬼。
本文就来探究几个最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。
而且，我们就是要深入细节，比如while循环中的不等号是否应该带等号，mid 是否应该加一等等。分析这些细节的差异以及出现这些差异的原因，保证你能灵活准确地写出正确的二分查找算法。
一、二分查找的框架
int binarySearch(int[] nums, int target) { int left = 0, right = ...; while(...) { int mid = (right + left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return ...; }
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。本文都会使用 else if，旨在讲清楚，读者理解后可自行简化。
其中...标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。
另外声明一下，计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2，本文暂时忽略这个问题。
二、寻找一个数（基本的二分搜索）
这个场景是最简单的，可能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1。
int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 while(left <= right) { // 注意 int mid = (right + left) / 2; if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; // 注意 else if (nums[mid] > target) right = mid - 1; // 注意 } return -1; }
1. 为什么 while 循环的条件中是 <=，而不是 < ？
答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。
这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。
我们这个算法中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间，我们不妨称为「搜索区间」(search space)。
什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：
if(nums[mid] == target) return mid;
但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。
while(left <= right)的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
while(left < right)的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就可能出现错误。
当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：
//... while(left < right) { // ... } return nums[left] == target ? left : -1;
2. 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？
答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。
刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？
当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。
3. 此算法有什么缺陷？
答：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。
比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的时间复杂度了。
我们后续的算法就来讨论这两种二分查找的算法。
另一种：
int search(int* nums, int numsSize, int target){ //定义左右指针 int left = 0; int right = numsSize; while (left < right) { int mid = left + (right - left) / 2; //刚好在中间找到时，直接返回中间下标 if (nums[mid] == target) return mid; //如果中间值比目标大，则在左边 else if (nums[mid] > target ) { right = mid; //如果中间值比目标小，则在右边 else left = mid + 1; } //未找到target，返回-1 return -1; }
三、寻找左侧边界的二分搜索
直接看代码，其中的标记是需要注意的细节：
int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意 while (left < right) { // 注意 int mid = (left + right) / 2; if (nums[mid] == target) { right = mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; // 注意 } } return left; }
1. 为什么 while(left < right) 而不是 <= ?
答：用相同的方法分析，因为初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。
while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 恰巧为空，所以可以正确终止。
2. 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？
答：因为要一步一步来，先理解一下这个「左侧边界」有什么特殊含义：
对于这个数组，算法会返回 1。这个 1 的含义可以这样解读：nums 中小于 2 的元素有 1 个。
比如对于有序数组 nums = [2,3,5,7], target = 1，算法会返回 0，含义是：nums 中小于 1 的元素有 0 个。如果 target = 8，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个。
综上可以看出，函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]，所以我们简单添加两行代码就能在正确的时候 return -1：
while (left < right) { //... } // target 比所有数都大 if (left == nums.length) return -1; // 类似之前算法的处理方式, target 如果比所有数都小 或者没有找到这个值也会返回 -1 return nums[left] == target ? left : -1;
3. 为什么 left = mid + 1，right = mid ？和之前的算法不一样？
答：这个很好解释，因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。
4. 为什么该算法能够搜索左侧边界？
答：关键在于对于 nums[mid] == target 这种情况的处理：
if (nums[mid] == target) right = mid;
可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
5. 为什么返回 left 而不是 right？
答：返回left和right都是一样的，因为 while 终止的条件是 left == right。
四、寻找右侧边界的二分查找
寻找右侧边界和寻找左侧边界的代码差不多，只有两处不同，已标注：
int right_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0, right = nums.length; while (left < right) { int mid = (left + right) / 2; if (nums[mid] == target) { left = mid + 1; // 注意 } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left - 1; // 注意
1. 为什么这个算法能够找到右侧边界？
答：类似地，关键点还是这里：
if (nums[mid] == target) { left = mid + 1;
当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。
2. 为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。
答：首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。
至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在这个条件判断：
if (nums[mid] == target) { left = mid + 1; // 这样想: mid = left - 1
因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left - 1]可能是target。
至于为什么 left 的更新必须是 left = mid + 1，同左侧边界搜索，就不再赘述。
3. 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？
答：类似之前的左侧边界搜索，因为 while 的终止条件是 left == right，就是说 left 的取值范围是 [0, nums.length]，所以可以添加两行代码，正确地返回 -1：
while (left < right) { // ... } if (left == 0) return -1; return nums[left-1] == target ? (left-1) : -1;
五、最后总结
先来梳理一下这些细节差异的因果逻辑：
第一个，最基本的二分查找算法：
因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1 因为我们只需找到一个 target 的索引即可 所以当 nums[mid] == target 时可以立即返回
第二个，寻找左侧边界的二分查找：
因为我们初始化 right = nums.length 所以决定了我们的「搜索区间」是 [left, right) 所以决定了 while (left < right) 同时也决定了 left = mid+1 和 right = mid 因为我们需找到 target 的最左侧索引 所以当 nums[mid] == target 时不要立即返回 而要收紧右侧边界以锁定左侧边界
第三个，寻找右侧边界的二分查找：
因为我们初始化 right = nums.length 所以决定了我们的「搜索区间」是 [left, right) 所以决定了 while (left < right) 同时也决定了 left = mid+1 和 right = mid 因为我们需找到 target 的最右侧索引 所以当 nums[mid] == target 时不要立即返回 而要收紧左侧边界以锁定右侧边界 又因为收紧左侧边界时必须 left = mid + 1 所以最后无论返回 left 还是 right，必须减一
如果以上内容你都能理解，那么恭喜你，二分查找算法的细节不过如此。
通过本文，你学会了：
1. 分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。
2. 注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。
3. 如需要搜索左右边界，只要在 nums[mid] == target 时做修改即可。搜索右侧时需要减一。
就算遇到其他的二分查找变形，运用这几点技巧，也能保证你写出正确的代码。LeetCode Explore 中有二分查找的专项练习，其中提供了三种不同的代码模板，现在你再去看看，很容易就知道这几个模板的实现原理了。
LeetCode练习：
53. 最大子数组和
53. 最大子数组和 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 int maxSubArray(int* nums, int numsSize){ int max = nums[0]; int sum = nums[0]; for(int i = 1; i < numsSize; i++) { if(sum < nums[i] && sum < 0) { sum = nums[i]; } else { sum += nums[i]; } if(sum > max) { max = sum; } } return max; }
69. x 的平方根
69. x 的平方根 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1： 输入：x = 4 输出：2 int mySqrt(int x) { if(x == 0){ return 0; } if(x == 1) { return 1; } int left = 0; int right = x; int mid; while(left <= right) { mid = left + (right - left)/2; if(mid == x/mid) { return mid; }else if(mid > x / mid) { right = mid - 1; }else if(mid < x/ mid) { left = mid + 1; } } if(mid < x / mid) { return mid; } else { return mid - 1; } }
367. 有效的完全平方数
367. 有效的完全平方数 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 进阶：不要 使用任何内置的库函数，如 sqrt 。 示例 1： 输入：num = 16 输出：true bool isPerfectSquare(int num){ if(num == 0 || num == 1) { return true; } long left = 0; long right = num; long mid; long square; while(left <= right) { mid = left + (right - left) / 2; square = mid * mid; if(square == num) { return true; } else if(square > num) { right = mid - 1; } else if(square < num) { left = mid + 1; } } return false; }
973. 最接近原点的 K 个点
973. 最接近原点的 K 个点 给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。 这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。 你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。 示例 1： 输入：points = [[1,3],[-2,2]], k = 1 输出：[[-2,2]] 解释： (1, 3) 和原点之间的距离为 sqrt(10)， (-2, 2) 和原点之间的距离为 sqrt(8)， 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。 int cmp(const void *aa, const void *bb) { int *a = *(int **)aa; int *b = *(int **)bb; return a[0]*a[0] + a[1]*a[1] - b[0]*b[0] - b[1]*b[1]; } int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes){ qsort(points, pointsSize, sizeof(points[0]), cmp); // *returnSize 是一个int 变量 *returnSize = k; // (*returnColumnSizes) 是一个 int* 的变量 (*returnColumnSizes) = malloc(sizeof(int) * k); int **res = malloc(sizeof(int *) * k); for(int i = 0; i < k; i++) { (*returnColumnSizes)[i] = 2; res[i] = malloc(sizeof(int) * 2); res[i][0] = points[i][0]; res[i][1] = points[i][1]; } return res; }
875. 爱吃香蕉的珂珂
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 // long类型，防止求和溢出 long hour_cnt(int *piles, int pilesSize, int speed) { long hour = 0; for (int i = 0; i < pilesSize; i++) { hour += (piles[i] + speed - 1) / speed; } return hour; } int minEatingSpeed(int* piles, int pilesSize, int h){ int left = 1; // 1 是最小速度 int right; int mid; int hour; // 计算右侧边界 for (int i = 0; i < pilesSize; i++) { right = fmax(right, piles[i]); } //二分 while (left <= right) { // 可以等于 right ,最大速度 mid = left + (right - left) / 2; // 防止溢出 hour = hour_cnt(piles, pilesSize, mid); if (hour == h) { right = mid -1; } else if (hour > h) { left = mid + 1; } else if (hour < h) { right = mid - 1; // 注意 } } return left; }
932. 漂亮数组
932. 漂亮数组 对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得： 对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。 那么数组 A 是漂亮数组。 给定 N，返回任意漂亮数组 A（保证存在一个）。 示例 1： 输入：4 输出：[2,1,4,3] 示例 2： 输入：5 输出：[3,1,2,5,4] void exec(int *arr, int size, int *tmp1, int *tmp2) { int i; int j = 0; int k = 0; //如果数组长度小于等于2 。不用处理 if(size <= 2) { return ; } //处理数组， 把数字 1 3 5 7放在前面， 把 2 4 6 8 放在后面 for(i = 0; i < size; i++) { if(i % 2 == 0) { tmp1[j++] = arr[i]; }else { tmp2[k++] = arr[i]; } } memcpy(arr, tmp1, j * sizeof(int)); memcpy(arr + j, tmp2, k * sizeof(int)); // 对前面 1 3 5 7 重复该处理 exec(arr, j , tmp1, tmp2); exec(arr + j, k , tmp1, tmp2); } int* beautifulArray(int n, int* returnSize){ int *arr; int *tmp1; int *tmp2; int i; *returnSize = n; //返回的数组 arr = (int *)malloc(sizeof(int) * n); //两个临时数组用来存放临时数据 tmp1 = (int *)malloc(sizeof(int) * n); tmp2 = (int *)malloc(sizeof(int) * n); for(i= 0; i < n; i++) { arr[i] = i + 1; } exec(arr, n, tmp1 , tmp2); free(tmp1); free(tmp2); return arr; }
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1： 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){ int i = matrixSize - 1; int j = 0; while(i >= 0 && j < *matrixColSize) { if(target < matrix[i][j]) { i--; }else if(target > matrix[i][j]) { j++; }else { return true; } } return false; }
1011. 在 D 天内送达包裹的能力
1011. 在 D 天内送达包裹的能力 传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。 返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。 示例 1： 输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5 输出：15 解释： 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 int dayCnt(int *weights, int weightsSize, int load) { int cnt = 0; int sum = 0; int i = 0; while(i < weightsSize) { sum = sum + weights[i]; if(sum > load) { cnt++; sum = 0; } else { i++; } } return cnt + 1; } /* //二分 while (left <= right) { // 可以等于 right ,最大速度 mid = left + (right - left) / 2; // 防止溢出 // 这里一开始错了， 重复加了 int 导致两个用例不过 hour = hour_cnt(piles, pilesSize, mid); if (hour == h) { right = mid -1;// 注意 } else if (hour > h) { left = mid + 1; } else if (hour < h) { right = mid - 1; } } return left; */ //典型二分法 ，求左边界 int shipWithinDays(int *weights, int weightsSize, int D){ int left = 0; int right = 0; int mid; int day; for(int i = 0; i < weightsSize; i++) { left = fmax(weights[i], left); right += weights[i]; } //二分查找 while(left <= right) { mid = left + (right - left) / 2; day = dayCnt(weights, weightsSize, mid); if(day == D) { right = mid - 1; // 求左边界，需要处理右 } else if(day > D) { left = mid + 1; } else if(day < D) { right = mid - 1; } } return left; }