今天想为大家带来基础算法的一部分也就是二分，我们在实现二分时的核心思想则是：不断地缩小搜索区域，降低查找目标元素的难度。当然，并不是所有的条件都可以使用二分的，所有可以使用二分查找法的题目有以下两个要求，一个是数列有序，另一个是数列使用顺序存储结构。
有单调性一定可以二分，可以二分的题目不一定有单调性
二分查找模板：
在这里我为大家列出二分查找的模板，这个模板也是二分查找的核心代码。
整数二分查找模板：
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; }
浮点数二分查找模板：
bool check(double x) double bsearch_3(double l, double r) { const double eps = 1e-6; while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
二分查找题目：
在这里我为大家列出两个题目来帮助大家学习二分查找
789. 数的范围
给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 nn 和 qq，表示数组长度和询问个数。
第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。
输出格式
共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例：
6 3 1 2 2 3 3 4 3 4 5
输出样例：
3 4 5 5 -1 -1
此题目可以用到我们上面列出的模板，而且可以帮助大家理解两个查找方法的区别，以+1出现的条件。
代码：
#include <iostream> #include <algorithm> using namespace std ; int a[100010] ; int main(void) { int n, q ; int num ; cin >> n >> q ; for(int i=0; i<n; i++) { cin >> a[i] ; } while(q--) { int num ; cin >> num ; int l=0, r=n-1 ; while(l<r) { int mid = (l+r)/2 ; if(a[mid] >= num) r=mid ; else l = mid+1 ; } if(a[l] != num) cout << "-1 -1" << endl ; else { cout << l << " " ; int l=0, r=n-1 ; while(l<r) { int mid = (l+r+1)/2 ; if(a[mid] <= num) l = mid ; else r = mid-1 ; } cout << r << endl ; } } return 0 ; }
790. 数的三次方根
给定一个浮点数 nn，求它的三次方根。
输入格式
共一行，包含一个浮点数 nn。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 66 位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
这道题目就是浮点数二分查找的模板应用
代码：
#include<iostream> using namespace std ; int main() { double x ; cin >> x ; double l=-100, r=100 ; double num = 1e-8 ; while(r-l >= num) { double mid = (l+r)/2 ; if(mid*mid*mid >= x) r = mid ; else l = mid ; } printf("%.6lf\n", l) ; return 0 ; }
希望大家看完这些题可以对二分查找能有更深的理解。二分查找这种方法实现代码并不难，在实现的过程中应注意一些细节，不要写成死循环。
