在算法中用的比较多的查找算法是二分查找，在这里梳理一下整数二分和浮点数二分的思路。
将来复习数据结构的话也会在这里补充。
二分查找
（一）是什么
二分查找（折半查找：Binary Search）的查找过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
注：
就算是找不到这个记录最终也是可以停下的，只不过停下的位置对应的值并不是想要的。
（二）优势
时间复杂度低：O(logn)
推导：
数据大小为n，每次查找后数据都会减半，最坏情况为直到区间数为1个时才停止，即：n * (1/2)的x次方 = 1
解得x = logn
（三）两个板子算法
首先必须清楚一件事，二分算法解决的本质是：寻找某一性质的边界，给出的两个板子就是找到性质1的右边界（箭头1）和性质2的左边界（箭头2）。
1.确定性质1的边界——找箭头1
mid = l + r + 1 >> 1
if(check(mid)): //判断是否满足该性质
- Ture
mid在箭头1的左边，那要找到箭头的话需要改变区间：l = mid，使[l, r] -> [mid, r] （包含mid，因为mid也满足性质。下同理）。 - False
mid在箭头1的右边，需要：r = mid - 1， 使[l, r] -> [l, mid -1]
2.确定性质2的边界——找箭头2
mid = l + r >> 1
if(check(mid)): //判断是否满足该性质
- Ture
r = mid, [l, r] -> [l, mid] - False
l = mid + 1, [l, r] -> [mid + 1, r]
板子如下：
注意：
1.l = mid时mid后面需要+1
2.这两个板子的返回结果就是两个边界
3.图中的性质1和性质2往往对应的是小于和大于
bool check(int x){/* ... */}
int bsearch_1(int l, int r){
//性质1
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return r; //此时l和r一样，返回谁都可以
}
int bsearch_2(int l, int r){
//性质2
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1
}
return l;
}
AcWing 789. 数的范围
这道题就是怎么用了。比如1 2 2 3 3 4问你3的起始位置和终止位置。（从0开始）
既然是有序的，那很轻易可以看出1 2 2 是<3的，4>3，我们可以将问题转化为寻找 <=3 右边界和 >=3 的左边界。
<=3 的右边界是位置4，>=3 的左边界是位置3， 很明显不是我们想要的答案。那我们直接颠倒顺序，寻找 >=3 的左边界 和 <=3 的右边界就可以解决问题。
如果寻找不到，那么边界位置的值一定不是寻找的值，一个if语句就可以解决。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n, q;
int main(){
scanf("%d%d", &n, &q);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
while(q --){
int k;
scanf("%d", &k);
//寻找k的左边界
//>=k的左边界，满足性质2
int l = 0, r = n - 1;
while(l < r){
int mid = (l + r) >> 1;
if(a[mid] >= k) r = mid;
else l = mid + 1;
}
if(a[l] != k) cout << "-1 -1"<<endl;
else{
printf("%d ", l);
//寻找k的右边界
//<=k的右边界，满足性质1
l = 0, r = n - 1;
while(l < r){
int mid = (l + r + 1) >> 1;
if(a[mid] <= k) l = mid; // l = mid 前面的mid应该+1
else r = mid - 1;
}
printf("%d\n", r);
}
}
return 0;
}
最常用的就是上面的整数二分板子了，浮点数二分更简单，没有+1-1的那些事儿。板子如下：
const double eps = 1e-6 ;一般定义的比题给的小两位
double bsearch_3(double l, double r){
while(r - l > eps){
double mid = l + r >> 1;
if(check(mid)) r = mid; //结合题
else l = mid;
}
return l;
}
eg.求三次方根
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8 ;//经验之谈，eps比题目要求的多两位
int main(){
double n;
scanf("%lf", &n);
double l = -10000, r = 10000;
while(r - l > eps){
double mid = (r + l)/2;
if(mid * mid * mid >= n) r = mid;
else l = mid;
}
printf("%lf", l); //double类型输出默认是6位，符合题目要求
return 0;
}
（四）哪些情况使用
这里谈论的就不仅仅是算法了，还有数据结构的一些东西。
- 存储的数据结构应该是可以实现随机访问的数组，而不是链表。（链表不支持随机访问）
- 数组内的数据必须有序
- 更适合处理静态数据（没有频繁的数据插入、删除操作）
- 太小的不适合，因为顺序查找就可以解决
- 太大的也不适合，因为二分底层依赖的就是数组，而数组在内存中就是一段连续的空间，你需要1G的空间，即使内存剩下2G可能也不够用，因为剩余的2G可能是离散分配后的结果，并没有1G的连续空间。
- 二分依赖的只有数组，所以大部分情况还是可以解决的。同时二分可以解决的散列表、二叉树也都可以解决。这些以后再补充，算法这里最常用的是二分。
下一个高精