二分法

二分查找的本质

二分查找往往用在一个有序排列的线性表中，查找某个元素，是否能够匹配。很容易让人理解为二分查找跟单调性关系很大，但实际上二分查找的本质是边界。 如果一个线性表中，可以通过某个条件将线性表一分为二，一边满足条件而另一边不满足条件。那么这个问题就可以用二分解决。

二分算法的实现

二分查找虽然很简单，但是实现起来往往容易出错。原因是其边界和条件的判断很容易出错。 这里的话就提供了两种类型的模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }

两种模板的适用条件可以总结为：如果仅仅试是求数组中某个元素是否存在，那么两种模板都是可以的，只是需要注意mid选取的时候，如果是向上取整那就要和mid + 1相适配。 假设要搜索的元素是x 而数组中存在多个x 那么我们要找到x位置的上界时，就需要用第二个模板，因为它在每次满足匹配条件以后，区间是往上收缩的。

例题

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围

1≤n≤1000001≤n≤100000

输入样例：

6 3 1 2 2 3 3 4 3 4 5

输出样例：

3 4 5 5 -1 -1 /*关于两个二分模板的话 就是如果只是判断能不能有匹配 两个都可以用 *然后写mid的时候先可以不加1 然后看后面的区间选取 如果用到mid + 1前面mid除以2的时候就不加1 *用到mid - 1前面就得加1 */ #include <iostream> const int N = 100000 + 10; int main() { int n = 0, q = 0; scanf("%d %d",&n, &q); int a[n]; for(int i = 0; i < n; i++) scanf("%d", &a[i]); int m = 0; while(q--) { scanf("%d",&m); //读取要查询的数 //求匹配数下界的二分 int l = 0, r = n - 1; while(l < r) //第一次二分寻找最左边的匹配 mid向下取整 { int mid = r + l >> 1; //另外这里是check满足条件的 所以取区间的时候要r=mid 把mid归进去。 if(a[mid] >= m) r = mid; //这个时候应该是往小的区间去寻找 即便相等也要再次缩小区间 else l = mid + 1;//不满足check条件可以直接放弃mid了 } if(a[l] != m) printf("%d %d\n", -1, -1); //如果没有匹配直接输出-1 -1 else { printf("%d ",l); //求匹配数的上界的二分 l = 0, r = n - 1; while(l < r) { int mid = r + l + 1>> 1;//mid向上取整 寻找最右边的匹配 if(a[mid] <= m) l = mid; else r = mid - 1; } printf("%d\n",r); } } return 0; }