前言： 二分查找虽然并不是什么很难的东西， 但因为我始终背不下来， 每次要用的时候都得现场小心翼翼地推导细节， 十分苦恼。因此希望通过写一篇笔记总结， 把它刻入我的记忆。
基本概念
不再赘述， 引用维基百科：
在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）[1]、对数搜索算法（英语：logarithmic search algorithm）[2]，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找的框架
二分查找的步骤大概是：
- 定义二分查找的左右边界
- 循环体， 循环条件一般为左边界不大于右边界
- 取中值（准确说是左右边界的平均值， 即中间元素）
- 用中值与查找的目标元素比较， 从而移动左右边界
二分查找的三种应用形式
通过对取中值以及对左右边界移动的细节处理， 可以得到不同功能的二分查找。
最朴素的二分查找
最朴素的二分查找的用法是： 查找某值是否在数组中出现过， 是则返回下标， 否则返回-1.
int binarySearch(vector<int> &nums, int l, int r, int target) {
while(l < r) {
int mid = (l + r) >> 1;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}查找左边界 / 第一个大于等于target的元素
在朴素二分中， 若数组中有多个值为target的元素， 返回的下标对于使用者而言是合理情况中的随机一个；若数组中中没有值为target的元素， 返回值将是无意义的-1.
接下来两种二分便是为了解决这一类问题。
在左边界二分中， 要查找的元素e满足：e左边的元素都小于target, e右边的元素及e都不小于（大于等于）target.
int binarySearch_lower(vector<int> &nums, int l, int r, int target) {
while(l < r) {
int mid = (l + r) >> 1;
if(nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}查找右边界 / 第一个小于等于target的元素
类似的， 在左边界二分中， 要查找的元素e满足：e右边的元素都大于target, e右边的元素及e都不大于（小于等于）target.
int binarySearch(vector<int> &nums, int l, int r, int target) {
while(l < r) {
int mid = (l + r + 1) >> 1;
if(nums[mid] <= target) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}细节1——取中值时的左偏和右偏
当[l, r]中有奇数个元素时如[1, 2, 3]， 中值显然为中间那个元素。 但当[l, r]中有偶数个元素时如[1, 2, 3, 4]， 中值到底是2还是3呢？
这就取决于mid的取法了
mid = (l + r) >> 1;
mid = (l + r + 1) >> 1;c++的中整数除法是与右移一位的效果完全相同的， 即整除， 当[l, r]中有偶数个元素时, 显然l + r为奇数， 所以(l + r) >> 1结果会偏向l这一边 而相反的(l + r + 1) >> 1会偏向r这一边。
取中的偏向是相当重要的问题， 若使用错误， 二分可能将陷入死循环。
在结论上， 可以简单的记忆为左边界左偏， 右边界右偏
细节2——左右边界的更新方式
边界二分与朴素二分很大的一个区别是： 朴素二分靠mid查找目标值， 若nums[mid] == target就立即返回； 而边界二分是靠不断缩小查找的区间， 最终区间长度为1时(l == r)， 区间中唯一的元素即为目标值。 以左边界二分举例
while(l < r) {
int mid = (l + r) >> 1;
if(nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}要找的是左边界， 当nums[mid] > target时， 是不能将r置为mid - 1的， 因为也许mid就是左边界； 类似的， 当nums[mid] == target时， 你不能确定mid左边是否是左边界， 但mid + 1往后的元素你可以确定一定不是左边界， 因此将r赋为mid， 缩小范围， 继续查找。 而只有当nums[mid] < target时， 才移动l， 此时mid显然不是左边界， 所以将l赋为mid + 1
补充1——取中值时的溢出
在区间较大情况下， 使用(l + r)直接取中值时可能会溢出整型范围。 所以可以用如下方式等价取代
mid = l + ((r - l) >> 1);
mid = l + ((r - l + 1) >> 1);补充2——查找失败
若要找第一个不小于target的元素， 但数组中所有元素都小于target? 此时l会不断向右移动， 直到移到到r的位置。 所以查找结束后， 可以在对结果进行一次判断， 如果不满足就返回-1.
int binarySearch(vector<int> &nums, int l, int r, int target) {
while(l < r) {
int mid = (l + r + 1) >> 1;
if(nums[mid] <= target) {
l = mid;
} else {
r = mid - 1;
}
}
return nums[l] <= target ? l : -1;
}二分查找的应用
二分查找最常见的应用就是在数组中查找某个值的左边界或右边界， 但还有一种的用法是浮点数二分， 必如求一个浮点数的n次方根。
给定一个浮点数 nn，求它的三次方根。
输入格式
共一行，包含一个浮点数 nn。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 66 位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例
1000.00输出样例
10.000000
思路
用二分的思想不断更新左右边界， 使左右边界逐渐逼近答案， 当左右边界足够接近答案时（达到精度要求）， 即认为左/右边界就是答案。
参考代码
# include <bits/stdc++.h>
using namespace std;
int main() {
double n; cin >> n;
double l = -100, r = 100;
while((r - l) > 1e-8) {
double mid = (l + r) / 2;
if(mid * mid * mid > n) {
r = mid;
} else {
l = mid;
}
}
printf("%.6lf\n", l);
return 0;
}