本文共 6065 字，大约阅读时间需要 20 分钟。
原贴地址：
写在前面
二分查找是一个非常基础的算法。但是完全掌握却并不容易。
首先再次介绍一下二分查找。大家开始学习二分的时候，总是伴随着一个万年不变的场景：有序数组(假设是升序)。
核心思路就是判断num[mid]。 但是大家一开始学的都会有三种情况。- num[mid] > target，就表示要找的数字一定位于mid左边，所以我们将右边界限制到mid-1，也就是right = mid - 1;
- num[mid] == target，刚好找到，返回mid。
- num[mid] < target，就表示要找的数字一定位于mid右边，所以我们将左边界限制到mid+1，也就是left = mid + 1;
这个例子非常好，确实讲出来了二分查找的核心思路，但忽略了许多细节。
在写二分查找的时候，是否总是写出来TLE（超出时间限制/死循环）？是否总是不能获得想要的答案？ 在看完这篇专题之后，一定能启发你有所思考。二分查找的特解
众所周知，一个通用的二分查找是不一定有特解的。
也就是说，在查找之前，我们是不知道数组中有没有我们需要查找的那个值的。也有可能有多个target，此时返回任意一个不确定的target的位置是没有意义的（这时候人们往往更加关系第一个target和最后一个target的位置）。 所以刚才介绍的num[mid] == target这种情况，是完全没有意义的。 在所有需要用到二分查找的工业/商业场景，没有人会去判断一个等于的情况。 我们就要总结出一个更通用的规律。将等于的情况并入大于或者是小于，也就是变成了大于等于和小于等于。
这样就将3种情况变成了两种情况，而且对于最终的结果没有任何的影响，不管是否有target我们都能返回，甚至在有多个target的时候，还能返回target的左边界和右边界。既然有左边界和右边界，我们需要如何操作才能返回左边界和右边界呢？如何在代码中区分这两种情况呢？
二分查找的“靠左”和“靠右”和边界
二分查找的中间值的取法也是一个很重要的细节。
我们一般使用的是mid=(left+right)/2，这样获得是靠左的中间值。 对于一个奇数长度的(由left和right包围的)数组来说，中间值只有一个，但是对于一个偶数长度的数组来说，中间值有两个，而且并不相同。 那么我们在两个中间值中，只能选取一个，那么这个选取的方法对于最终的结果有影响吗？
我们设想这么一个场景，假设二分到了最后一步，此时只剩下两个数了。
如果我们“靠左”取mid，那么就会出现如上图所示的情况，如果我们的代码像下面一样，肯定是不可行的： if (条件成立) { left = mid;} else { right = mid;} 这样mid一直都没有变动，就会陷入死循环。
所以我们应该做如上改动：if (条件成立) { left = mid + 1;} else { right = mid;} 这样就不会死循环了，但是在我们上述修改过后的代码找出来的最终元素是什么呢？相信思路快的同学已经看出来了，我们找到的是条件不成立的最靠左的数字。
那么如果我们想要找条件成立的最靠右的数字呢？
有两种办法，一种是对于刚刚找出来的条件不成立最靠左的数字，减1，就是条件成立最靠右的数字。第二种办法是从二分查找入手。全部反一下。也就是说，代码应该写成这种形式：if (条件成立) { left = mid;} else { right = mid - 1;} 而写成这种形式无可避免地就要求我们取靠右的mid。
所以我们总结一下
| mid取向 | left | right | 最终结果 |
|---|---|---|---|
| 靠左 (left+right)/2 | mid+1 | mid | 条件不成立的最靠左的数字 |
| 靠右 (left+right+1)/2 | mid | mid-1 | 条件成立的最靠右的数字 |
只有这两种情况是合理合法的二分查找标准形式。
二分查找的条件
那么我们就可以很轻松的回答上面的问题了，如果一个数组里有许多target，我们想获得最左边的target该怎么做呢？
在这种情况下，我们可以取小于target作为我们的边界，因为在这个最左边的target左边，就是一条分界线。
在这个分界线的左边，所有的数字都小于target,在这个分界线的右边，所有的数字都大于等于target。
所以我们就可以直接把这个条件简单替换至上面的if(条件成立)处。
说了这么多理论，来看一下实战吧！
No.278 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
思路分析
非常简单，三步走：
1.把isBadVersion()看成一个数组，数组中靠左的是false,靠右的是true，所以条件成立就是isBadVersion()==false
好了，非常清晰，对照表格中，选用的是mid靠左取的情况。
啪的一下就写完了代码。C++代码
class Solution { public: int firstBadVersion(int n) { int left = 1, right = n; while (left < right) { int mid = left + (right - left) / 2; if (isBadVersion(mid) == false) { left = mid + 1; } else { right = mid; } } return left; }}; 这里给大家一个小建议，千万不要把left和right倒过来写，为了思路清晰，建议一定要把数组靠左成立的条件写到if里，在此时，第一行一定是left=啥啥啥。这样不太容易出错。举个不建议的例子：
if (isBadVersion(mid) == true) { right = mid;} else { left = mid + 1;} 这么写和上述是等价的。但要是你不是很会，建议还是老老实实写个==false。
很轻松啊！继续来看第二题
No.374 猜数字大小
猜数字游戏的规则如下：
- 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
- -1：我选出的数字比你猜的数字小
pick < num - 1：我选出的数字比你猜的数字大
pick > num - 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！
pick == num
返回我选出的数字。
示例 1：
输入：n = 10, pick = 6输出：6
示例 2：
输入：n = 1, pick = 1输出：1
示例 3：
输入：n = 2, pick = 1输出：1
示例 4：
输入：n = 2, pick = 2输出：2
提示：
1 <= n <= 231 - 11 <= pick <= n
老方法，看成数组，形状应该是[…,1,1,1,0,-1,-1,-1,…]
1.条件都不用说了吧，不过有两种取法，一种是取大于等于0最靠左的，一种是取小于等于0最靠右的，怎么取都能对。 2.下面都不用写了直接看表吧！ PS:这个题由于有特殊值，可以使用特殊值特判。但是不建议这么做，应该尽量选一个通用的方法做熟练。并非所有情况都有特殊值，但就算有特殊值也可以用1中的方法看成没特殊值来做C++代码
靠左做法：
class Solution { public: int guessNumber(int n) { int left = 0, right = n; while (left < right) { int mid = left + (right - left) / 2; if (guess(mid) > 0) { left = mid + 1; } else { right = mid; } } return left; }}; 靠右做法：
class Solution { public: int guessNumber(int n) { long left = 0, right = n; while (left < right) { long mid = left + (right - left + 1) / 2; if (guess(mid) > -1) { left = mid; } else { right = mid - 1; } } return left; }}; 特殊值做法（不推荐）：
class Solution { public: int guessNumber(int n) { long left = 0, right = n; while (left < right) { long mid = left + (right - left) / 2; if (guess(mid) == 0) { return mid; } else if (guess(mid) == 1) { left = mid + 1; } else { right = mid - 1; } } return left; }}; No.852 山脉数组的峰顶索引
符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3- 存在
i（0 < i < arr.length - 1）使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
示例 1：
输入：arr = [0,1,0]输出：1
示例 2：
输入：arr = [0,2,1,0]输出：1
示例 3：
输入：arr = [0,10,5,2]输出：1
示例 4：
输入：arr = [3,4,5,1]输出：2
示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]输出：2
提示：
3 <= arr.length <= 1040 <= arr[i] <= 106- 题目数据保证
arr是一个山脉数组
进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
思路分析
这一题不用想直接二分，关键又回到了条件，山脉数组究竟有什么条件呢？我们假设仍然存在一条分界线，这个分界线左边的num[mid]满足什么条件呢？可以看出，数组的总体趋势是先上升后下降的。
其实也很好想，满足的就是num[mid] > num[mid-1]，而分界线右边的数字都不满足。 在此时，我们要求的就是满足条件最靠右的第一个元素。 所以其实就可以查表了C++代码
class Solution { public: int peakIndexInMountainArray(vector & arr) { int left = 0; int right = arr.size() - 1; while (left < right) { int mid = (left + right + 1) / 2; if (arr[mid] > arr[mid - 1]) left = mid; else right = mid - 1; } return left; }}; 其实也是一样的道理，都很简单，只要我们理清了那个表的道理，做一切二分问题都能迎刃而解。
转载地址：http://cuuci.baihongyu.com/