二分查找一般用于在有序数组中查找某个特定的值。一般来说，它需要确定 low 与 high 用于限定每轮迭代的范围，用 mid 位置处元素与 target 比较 ，从而降低每轮迭代的搜索空间。由于每次降低的空间大小为原搜索空间大小的 1/2，因此，它的时间复杂度往往和 O(log n) 相关。
一般性的模板：
int lo = ini_value;
int hi = end_value;
while (lo < hi){
int mid = (lo+hi)/2; // 最佳写法：mid = lo+(hi-lo)/2，避免越界，/2 也可改为 >> 1，但是要注意运算符优先级
if (nums[mid] < x){ // 排除一定要排除的情况
lo = mid+1; // lo=mid+1，可以避免死循环
} else {
hi = mid; // hi=mid，用于已经找到 target 的情况下，hi 向 lo 逐渐逼近
}
}
return lo;注意：并不是说 lo 一定要 +1，hi 一定用作逼近，这样看取怎么样的分割区间。
一般来说，将区间一分为二，在一分为二的基础上排除一个区间是二分查找的任务：
上述方式对应的区间选择如上图所示，在 mid 处将搜索空间一分为二。也可以将划分点提到右部，如此，lo 与 hi 将进行如下更新：
lo = mid;
hi = mid-1;注：例题均来自与力扣，可对应题目名称搜索以进一步详细了解。
注：这道题目将使我们修改一般性模板，是 lo <= hi 的典型情况。
首先，sqrt(x) 必然位于 [0, x] 之间。考虑:
我们先不对此边界情况写处理代码，而是在写完处理大部分情况的代码后，设计符合上述三个边界情况的用例作为验证。套用上面的模板，以下代码可轻松写出：
class Solution {
public:
int mySqrt(int x) {
int lo = 0;
int hi = x;
int res = 0;
while (lo <= hi){
int mid = lo+(hi-lo)/2;
if ((long)mid*mid <= x){
res = mid;
lo = mid+1;
} else {
hi = mid-1;
}
}
return res;
}
};现在考虑边界情况：
首先，题目要找的结果，要么是 x%lo == 0 && lo*lo == x，要么是 x%lo != 0 && lo*lo < x。例如：2*2 == 4, 3*3 == 9 > 8（return 2*2）。 也就是说，我们找到的 lo，有可能出现 lo*lo > x 的情况，因为在 mid*mid <= x 时，我们做了 lo=mid+1 的操作，而我们要找的是符合情况二的值，因此，在 mid*mid <= x 时，我们总是记录该 mid 值，而 lo 更新为 mid+1。如此，在下一轮迭代中，要么新的 mid*mid > x，由此我们返回正确的 res，此时的 res 恰好符合情况二，要么新的 mid*mid <= x，继续上述步骤。
无论如何，在每轮迭代中，要么 hi = mid-1 要么 lo = mid+1，两种操作只能执行一种，所以毋容置疑 hi 和 lo 一定会相遇。而我们由上述分析得出，lo 与 hi 相遇时的值不一定就是我们要求的值。
先做第一个分析，我们需要 lo == hi 时的值，进行进一步的判断。那么 hi = mid-1 是必然的，因为若不如此做，我们的退出条件是 lo <= hi，如果 hi 一直做 mid 而不是 mid-1 的进逼，我们很可能陷入 hi == lo && hi = mid 的无限循环中。
上述分析是由结果分析缘由，对做题意义不大，我们需要正向的思维做出推导。首先，我们设置 (long) mid*mid <= x，也就是说，mid 将有三种取值情况：
其中，情况一和情况二才有可能是 res，情况三不可能得出 res。也就是说，在必然能得出结果的搜索空间中，我们令 lo=mid+1，这就有可能导致 lo*lo > x 的情况。注意：分析 lo 正好处于 res 和 res+1 的边界处的情况：
很明显，情况一是我们要的答案，在情况一的条件下，我们可以借由 lo = mid+1 退出循环，并保存 mid 到 res 中，是为正确结果。但是如果遇到情况二呢？此时 lo*lo > mid，如果 hi = mid，我们将处于一个无限循环中，而我们已经得到了 res 的值，需要退出循环（因为上一轮迭代，res 已经记录了 mid*mid 恰巧小于 x 的情况）。因此，hi 需要进行 -1 逼近（逼近 lo-1），而不是逼近 lo（因为循环条件是 lo <= hi，== 时也将进行循环）。
因为此二分法是在 [0, x] 内做循环，而 x 是个非负整数，对其中的 mid 做乘方操作是极有可能越界的。事实上，我们不常见到数组的大小超出 INT_MAX，而未对 mid （此时表示 index）做出越界处理。为了考虑越界，mid = lo+(hi-lo)/2 是极为周全的取中措施，不管是否是数组下标循环还是整数范围内循环。
注意：我们使用了 long 转换来应付越界情况，那如果 x 是 long long 以及更大的数呢？因此，上述的越界处理并不够好，而是一个利用题目漏洞的做法，不足以应付所有情况。
下面的代码是更佳的选择：
class Solution {
public:
int mySqrt(int x) {
if(x == 0)
return 0;
int low = 0,high = INT_MAX/2;
while(low < high){
int mid = (low + high)/2;
if(mid > x/mid)
high = mid;
else if(mid < x/mid)
low = mid+1;
else
return mid;
}
return low-1;
}
};实际上，退出循环与 low 和 high 的更新紧密相关，我们需要程序正确的退出循环即可，而在退出循环后，再对值进行修正也未尝不是一种选择。
我们每次只在 mid > x/mid 的情况下使 high = mid，而 mid = (low+high)/2（向下取整），这就使得 high 终将与 low 相等，也就是说，如果 hi 在此条件下以此方式更新，循环是可以退出的。
在每次 mid < x/mid 的情况下，我们使 low = mid+1。那么存在这么一种可能：x%mid != 0，并且 mid 恰恰是我们寻找的结果。在此处，我们不仅可以保证 low = res+1，也可以保证最终的 hi = res+1（因为我们使 high 靠近 low）。那么，我们只需要考虑最后一种情况了：mid = mid/x。实际上这种情况也包含两种小情况：
x%mid == 0 && mid*mid == x
x%mid != 0 && mid*mid < x（由 保证结果的正确性，可以取一些例子直观感受：9/3 == 3, 10/3 == 3, 11/3 == 3）
不管是哪一种，都是我们需要的答案。
由上述两种处理，我们要么拿到正确答案 mid，要么拿到比正确答案稍大的数，进行修正（return low-1）。同时，我们更为合理地处理了越界情况。因此，该方法是为更好的办法。
以小见大：
模板仅仅作为一种类似于框架的综合处理流程，具体如何处理，实际上是相当灵活的，不必拘泥于哪种格式，但一定要擅长一种格式。在该格式下，考虑：
注：此题是典型的部分数组元素有序（一般是数组发生旋转）的情况下使用二分查找。
一个大的升序数组被分为两个小的升序数组，在旋转点处，数值将做高到低的变化。
这种旋转数组有一个重要特性，它是可以通过旋转点将失序数组映射为原始升序数组的：
cur_idx = (real_idx+rotation) % length
如下图所示，原来的数组 real 在 index = 6 处发生旋转：
对于原数组 index = 6 的位置，原本存储着元素 7，现在 7 的位置位于旋转后数组 cur 的 index = 2 处：
real: real[6] = 6
cur: (6+6)%10 = 2
real[6] <--> cur[2]由此，我们先求出旋转位置，然后以映射的方式在原升序数组中寻找 target 的位置：
由上图不难得出规律：对于 mid 位置元素来说，如果 mid 和 lo 的值有序，说明左半端区间是连续且有序的，如果 mid 和 hi 的值有序，说明右半端区间是连续且有序的。而数组总会在某个地方发生旋转，那么，如果左半端区间有序，旋转点必然在右部的某个位置出现，如果右半端区间有序，旋转点必然在左部的某个位置出现。
但是我们说，一定将必然要执行的逻辑写在前面，如果 mid 和 hi 位置元素失序（nums[mid] > nums[hi]），那么，旋转点必然在 mid 右侧出现，对于 mid 和 lo 失序来说道理也是一样。那么，代码的核心逻辑便由上述句子转换为代码：
if (nums[mid] > nums[hi]){
lo = mid+1;
} else {
hi = mid;
}考虑上图数组，real 的初始 mid（mid = 4） 元素在 cur 的什么位置？
(4+6)%10 = 0也就是说，real 的初始 mid 元素应该位于 cur 数组的 index = 0 处。那么，如果我们每轮都使 mid 映射在正确的位置上，就相当于我们在原数组上进行了有效地二分查找。完整代码如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0;
int hi = nums.size()-1;
// 找到旋转点
int rot = 0;
while (lo < hi){
int mid = (lo+hi)/2;
if (nums[mid] > nums[hi]){
lo = mid+1;
} else {
hi = mid;
}
}
rot = lo;
// 执行二分查找
int len = nums.size();
lo = 0;
hi = len-1;
while (lo <= hi){//边界用例[4,5,6,7,0,1,2], 0
int mid = (lo+hi)/2;
int real_mid = (mid+rot)%len;
if (nums[real_mid] < target){
lo = mid+1;
} else if (nums[real_mid] > target){
hi = mid-1;//边界用例[4,5,6,7,0,1,2], 3
} else {
return real_mid; // 返回的下标一定是映射后的 mid，因为我们一直在以 real 中的下标进行查找，而应该返回的是对应的 cur 中的下标
}
}
return -1;
}
};同样的，二分法十分灵活，对于设置不同的退出循环条件，和逼近策略，只要考虑好特殊边界情况，同样可以得到正确的结果。接下来给出第二种方法，选择自己熟练的才是最好的：
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()){ // 边界用例 [], 100
return -1;
}
int lo = 0;
int hi = nums.size()-1;
// 找到旋转点
int rot = 0;
while (lo < hi){
int mid = (lo+hi)/2;
if (nums[mid] > nums[hi]){
lo = mid+1;
} else {
hi = mid;
}
}
rot = lo;
// 执行二分查找
int len = nums.size();
lo = 0;
hi = len-1;
while (lo < hi){
int mid = (lo+hi)/2;
int real_mid = (mid+rot)%len;
if (nums[real_mid] < target){
lo = mid+1;
} else {
hi = mid;
}
}
lo = (lo+rot) % nums.size(); // 返回的下标一定是映射后的 lo
return nums[lo] == target ? lo : -1;
}
};注：该题是典型的在无序数组中寻找相对有序对的情况
首先考虑峰值的情况：
题目要求找到一个峰值即可，而不是说找到特点的某个峰值，在这种弱化的要求下，我们才能使用二分法查找一个峰值。
在情况 1、2 下，不必说二分查找可以非常顺利的执行。而在情况 3 下，为什么也可以使用二分查找找到峰值呢？
但问题在于，数组可能是由多个这样的区间组成的，杂乱无章，如何保证二分查找是有效的呢？
首先我们要明确一点：在无序数组中使用二分查找寻找一个特定的值是不可行的。题目要求找到任意峰值正是如此。
其次，为何我们总能使用二分查找找到一个正确的区间，从而进一步找到峰值？
我们知道，虽然数组是乱序的，但是对于一个峰值区间来说，如果 mid 元素与 mid+1 元素呈升序，那么峰值必然在区间 [mid, hi] 出现。如果 mid 元素与 mid+1 元素呈降序，那么峰值必然在区间 [lo, mid] 出现。
这样仍然不好理解，我们可以使用导数思维：
我们只研究一种情况，就是峰值出现在中间的情况。完全可以假设，左边界处导数大于 0 而右边界处导数小于 0（因为中间必然存在峰值，使得曲线导数为0）。对应到一条曲线便是：
以此图为例
如果：
那么，区间 (mid+1, hi) 存在一个值 x，x 满足：
如果：
那么，区间 (lo, mid+1) 存在一个值 y，y 满足：
因此，我们可以使用二分查找策略寻找不指定的一个峰值。
即使如此，那么为什么二分查找一定能在此题目起到效果呢？换句话说，我们已经知道存在一处峰值的情况下，确实可以用二分查找找到该峰值。但是曲线是波浪起伏的，有若干个峰值，如何保证自己的算法一定在 O(log n) 呢？
我们注意到，在每轮迭代中 mid+1 处的导数情况总能使我们确定当前迭代所要查找的峰值在哪个区间，也就是说，至少，我们在当前一轮迭代中，可以把搜索空间缩小一倍。此时，我们抛弃一半搜索空间，剩下的一半搜索空间作为我们下一轮的全部搜索空间。此时，我们来到下一轮迭代。我们注意到，搜索空间两端的导数情况与上一轮的情况是一样的，即使我们所要搜索的峰值可能已经和上一轮不一样了，但是，我们同样可以使用 mid+1 处的导数情况，再把此轮迭代的搜索空间缩小一倍，逼近一个全新的峰值。如此，每轮迭代我们总能使搜索空间减小一倍，同时逼近一个峰值（它的值可能一直在变化，但我们只关心导数情况）。那么我们的二分策略必然能生效，并达到 O(log n) 的时间复杂度。
题目的要求是 nums[i] ≠ nums[i+1]，那么峰值一定大于左右两端的数，也就是说，如果 nums[mid] < nums[mid+1]，我们必然要让 lo 往逼近 hi，对应模板便是 lo = mid+1。而对于 nums[mid] > nums[mid+1] 的情况，很可能此 mid 就是峰值了，那么我们让 hi 往 lo 逼近便是。由 mid = lo+(hi-lo)/2 可知，hi 终将靠近该 mid。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int lo = 0;
int hi = nums.size()-1;
while (lo < hi){
int mid = (lo+hi)/2;
if (nums[mid] < nums[mid+1]){
lo = mid+1;
} else {
hi = mid;
}
}
return lo;
}
};注：此题是 (lo+hi)/2 越界的典型情况，实质上类似于有序数组旋转
试想，我们在遇到旋转数组时，通过 nums[mid] 与 nums[lo] 的比较，我们可以知道 [lo, mid] 是否有序，从而知道旋转点（失序的起始位置）位于哪一半区间。对于 nums[mid] 与 nums[hi] 同样是如此。
而此题中，我们大可把 isBadVersion(int version) 函数等同于 nums[mid] 与 nums[hi]（或者 nums[lo]）的比较，因为，我们通过调用 isBadVersion(mid_version) 就可以知道 [lo, mid_version] 是否有序（即，该区间内所有 version 正确），从而得出失序开始的位置处于哪一半区间（即，从该位置到末尾的区间内，所有 version 错误）。
我们要找的是第一个错误 version，因此，我们应该保证见到正确的 version，lo 向前推进（因为你不能让 lo 停留在正确 version 的位置）；而遇见错误的 version 时，我们应该考虑到让 hi 停留在该 version 的可能（因为这可能就是我们要找的 version）。因此，对于 lo 我们应选择的是步进（=mid+1），对于 hi 我们应选择的是逼近（=mid）。
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int lo = 0;
int hi = n;
while (lo < hi){
int mid = lo+((hi-lo)>>1);
if (isBadVersion(mid)){
hi = mid;
} else {
lo = mid+1;
}
}
return lo;
}
};注：此题较好地考验了逼近策略的灵活使用
此题要求我们使用两种策略（并不一定是这两种策略）：
注：这两种策略都是基于向下取整（mid = (lo+hi)/2）
首先，我们需要找到开始位置，因为 mid 使用向下取整，所以我们只能使用 hi 来逼近 lo，而不能用 lo 逼近 hi，因为那会造成无限循环。
然后，我们需要找打结束位置，因为 mid 使用向下取整，所以我们可以使用 lo 步进，这样一定能使 lo 处于结束位置的下一位置。随后我们再纠正 lo 的位置即可。
以这种方式写的代码如下：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res{-1, -1}; // 边界用例 [], 100
if (nums.empty()){
return res;
}
int lo = 0;
int hi = nums.size()-1;
while (lo < hi){
int mid = lo+hi>>1;
if (nums[mid] >= target){ //我们要找到该元素的初始出现位置，显然不应该使用步进，而应使用逼近
hi = mid;
} else {
lo = mid+1;
}
}
if (nums[lo] == target){ // 第一次二分查找找到开始位置
res[0] = lo;
} else { // 第一次二分查找没找到开始位置意味着数组中并没有此元素
return res;
}
lo = 0;
hi = nums.size()-1;
while (lo < hi){
int mid = lo+hi>>1;
if (nums[mid] > target){
hi = mid;
} else { //我们要找到该元素的最后出现位置，显然应该使用步进，而不应使用逼近
lo = mid+1;
}
}
if (nums[lo] == target){ // 使用逼近策略意味着我们肯定走向了最后出现位置的下一位置，我们需要矫正它
res[1] = lo; // 情况1：最后出现位置同时也是数组结束位置，那么我们就不需要矫正了
} else {
res[1] = lo-1; // 情况2：最后出现位置同时不是数组结束位置，那么我们需要矫正其位置-1
}
return res;
}
};二分法非常灵活，我们并不一定使用上述策略：
注：这种策略基于向下取整和向上取整（mid = (lo+hi+1)/2）
寻找起始位置不在赘述。对于寻找结束位置，我们使用向上取整，并使用 lo 去逼近（向下取整时只能用 hi 逼近），如此最后得出的结果不需要纠正，必定位于结束位置，而不是位于结束位置的下一位置。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res{-1, -1}; // 边界用例 [], 100
if (nums.empty()){
return res;
}
int lo = 0;
int hi = nums.size()-1;
while (lo < hi){
int mid = (lo+hi)>>1; //向下取整
if (nums[mid] >= target){ //用 hi 逼近
hi = mid;
} else {
lo = mid+1;
}
}
if (nums[lo] == target){ // 第一次二分查找找到开始位置
res[0] = lo;
} else { // 第一次二分查找没找到开始位置意味着数组中并没有此元素
return res;
}
lo = 0;
hi = nums.size()-1;
while (lo < hi){
int mid = (lo+hi+1)>>1; // 向上取整
if (nums[mid] <= target){ // 用 lo 逼近
lo = mid;
} else {
hi = mid-1;
}
}
res[1] = lo; // 无需调整
return res;
}
};以小见大：
取整方法与逼近策略息息相关。灵活的使用的前提是清楚它们之间的关系。我们通过分析无限循环的情况，来揭示取整与逼近：
如果采用向下取整：
mid = (lo+hi)/2
我们注意到，lo 与 hi早晚会相邻（值相差 1），这是由 /2 带来的，但能不能相遇，就要看临界时（值相差 1）的操作了。如果临界时（hi = lo+1），使用的是 lo = mid 策略（lo 逼近策略），那么代入 hi = lo+1，mid = (lo+lo+1)/2 = lo，也就是说，lo 的值将不会被更新，而处于无限循环的状态。而使用 hi = mid 策略（hi 逼近策略）就不会产生这种情况，因为，代入 hi = lo+1，mid = (lo+lo+1)/2 = lo，这意味着 hi 在不断向 lo 靠近，它的最终目的就是要等于 lo。
类似的我们可以分析出向上取整时的逼近策略，此处极为重要，一定要分析好用哪种取整手段，哪种逼近策略，如此方才能随机应变。
注：此题考察排序规则的灵活变换
首先我们考察所有距离对可能的取值情况：
1 + 2 + 3 + ... + n-1 = n*n / 2
在 n 个元素中，每个元素与其他 n-1 个元素构成 n-1 个距离对，但是因为距离是无向的，真正的距离元素对并没有这么多。去除重复后，最多可能取值情况为 n*n / 2。
也就是说，我们的搜索空间大小为 n*n / 2，我们要在这个搜索空间上找出第 k 小的值。此时，我们有了 lo 与 hi。
我们仍需要 mid 与 一个 target 比较，target 代表着第 k 小的距离对。从这个思路上讲，因为距离对取值是无序的，我们需要先将所有距离对排序，再取排序后的第 k 个元素。时间复杂度将是 O(n^2)。
如何降低时间复杂度呢？必须从排序原则下手。target 代表着第 k 小的距离对，换句话说，对于一个距离 x 来说，如果 x 使 k -1 个距离小于它，那么它就是第 k 小的距离对。也就是说，小于某个距离的距离对的个数，可以作为排序准则。同时，target 更新为小于 k 个距离的距离对的个数。
在此思路下，我们需要知道距离对的最大取值情况。不妨花费时间给数组排序，最大元素减去最小元素即为 hi，lo 取 0 即可。
我们需要获得小于距离 t 的距离对的个数。此时数组已然排序，找到小于距离 t 的距离对的个数带来的花费将大大下降。假设 l 与 r 代表着一个元素对，其中 r > l。因为数组是已排序数组，我们让 r 从 0 到 nums.size() 循环，如果 nums[r]-nums[l] > t，我们就将 l 进行 ++ 操作，因为 nums[l] 越来越大，所以 nums[r]-nums[l] 越来越小，这意味着，r-l 个数将使 nums[r]-nums[l] <= t。
由此，我们求得了一轮循环中，r-l 个距离对符合要求。下一轮循环中 r 将变为 r+1 继续上述操作。那么，为什么 l 的值不用像 r 那样迭代呢？
r 在逐渐增大，这意味着 nums[r] 越来越大，因为数组是有序的，那么，我们还需要考虑让 l 从 0 开始计算吗？我们在上轮迭代就得出了一个 l，使 nums[r]-nums[l] <= t，在本轮中 nums[r] 已然随着 r 增大，而我们需要的是距离差值 <= t 的个数（当nums[r]-nums[l] > t 时，我们让 l 做 ++），。这意味着，l 根本不需要从 0 开始，从上轮迭代的位置开始就好。这一步的时间复杂度是O(log n)。整个算法的时间复杂度将是 O(n log n)。
根据以上思路可以写出如下代码：
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int lo = 0;
int hi = nums[nums.size()-1]-nums[0]; //最大距离
while (lo < hi){
int mid = lo+(hi-lo)/2;
if (count(nums, mid) < k){ //距离小于 mid 的距离对的个数小于 k 个时，严格步进
lo = mid+1;
} else { //距离小于 mid 的距离对的个数 >= k 个时，可能已经取得了正确答案，逼近即可
hi = mid;
}
}
return lo;
}
int count(vector<int>& nums, int t){ //距离小于 t 的距离对的个数
int res = 0;
int l = 0; // 由于数组已经排序，l 不需要每次从 0 计起
for (int r = 0;r < nums.size();++r){
while (nums[r]-nums[l] > t){ // 舍弃距离大于 t 的距离对
++l;
}
res += r-l; //从 l 之后距离对均 <= t
}
return res;
}
};接下来我们将对一些题目进行分类汇总。
此部分持续更新... ...