文章目录
前言
一、二分查找法[整数]
1.例题：AcWing 789. 数的范围
2.本题代码：
(1)本题核心部分详解:
(2)AC代码：
二、二分查找法[浮点数]
1.例题：AcWing 790. 数的三次方根
2.AC代码：
三、二分查找的代码模板：
1.整数二分：
2.浮点数二分模板：
四、时间复杂度的分析：
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：二分，关于二分查找法的时间复杂度的分析，以后会补充到本博客中，目前先鸽了，对于题目的代码不做过多解释，二分查找中每一行代码的详细见二分查找的模板
一、二分查找法[整数]
1.例题：AcWing 789. 数的范围
这里结合具体的习题去讲解二分，并且给出代码模板：二分例题的链接：AcWing789.数的范围
本博客给出本习题的截图：
2.本题代码：
代码如下：
(1)本题核心部分详解:
/* 写之前明确自己要求什么 假设查找x的坐标，本题输出中的第一个数为≥x的最小位置，第二个输出为≤x的最大位置 如果没有该元素就输出“-1 -1” 对于查找≥x的最小位置： */ int l = 0, r = n - 1; //题意从0开始为起始坐标，故终点坐标为n - 1 while(l < r) { int mid = l + r >> 1 //等同于 mid = (l + r) / 2; if (q[mid] >= x) //q[mid]就是二分后的最中间的数 //q[mid]如果≥x，我们要找的是≥x的最小位置 //即我们要找的位置在mid的左边或就是mid（当只有一个数的时候） r = mid; //故我们要更新r，使得r = mid; else //即q[mid] < x，而我们要找的是≥x的数，即要找的在mid的右边 l = mid + 1; //故更新l为mid + 1 } /* 此时我们的l，或者是r就是我们要找的起始坐标 输出起始坐标还有一个问题：如何保证我们真正的找到了这个数 */ if (q[l] != x) printf("-1 -1"); //如果我们真正的找到了这个数，那么我们的q[l]或是q[r]应该是等于我们要查找的数字x的 //所以有该if语句，即如果不等于的话，就输出"-1 -1" //接下来去查找≤x的最小位置： int l1 = 0， r1 = n - 1； //这里的l1我们可以从0开始，也可以从l开始 while (l < r) { int mid = l + r + 1 >> 1; //等同于 mid = (l + r + 1) / 2 //至于这里为什么要写成(l + r + 1) / 2，见代码模板 if (q[mid] <= x) //q[mid]如果≤x，我们要找的是≤x的最大位置 //即我们要找的位置在mid的右边或就是mid（当只有一个数的时候） l = mid; //故我们要更新l，使得l = mid; else //即q[mid] > x，而我们要找的是≤x的数，即在mid的左边 r = mid - 1; //故更新r为mid - 1 }
(2)AC代码：
#include <iostream> using namespace std; const int N = 100010; int q[N]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i ++ ) cin >> q[i]; while (m -- ) { int k; cin >> k; int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (q[mid] >= k) r = mid; else l = mid + 1; } if (q[l] != k) cout << "-1 -1" << endl; else { cout << l << ' '; int l1 = 0, r1 = n - 1; while (l1 < r1) { int mid = l1 + r1 + 1 >> 1; if (q[mid] <= k) l1 = mid; else r1 = mid - 1; } cout << r1 << endl; } } return 0; }
二、二分查找法[浮点数]
1.例题：AcWing 790. 数的三次方根
例题连接：数的三次方根
本博客给出本习题的截图：
2.AC代码：
代码如下：
#include <iostream> using namespace std; int main() { double x; cin >> x; double l = -10000, r = 10000; //因为要通过二分去求，左右端点直接赋值成题目中给定的n的范围边界 while (r - l > 1e-8) //当所求l和r十分接近的时候，即可求出³√x的值 //题目中要求保留6位小数，故这里写成1e-8最为保险（高题目要求2个精度） //即题目若要求四位小数的话，写成1e-6，以此类推 { double mid = (r + l) / 2; if (mid * mid * mid >= x) r = mid; //证明³√x ≤ mid，即所求在mid左边，故 r = mid else l = mid; } printf("%.6lf", l); return 0; }
三、二分查找的代码模板：
本模板来自AcWing的y总-算法基础课，AcWing链接：AcWing
1.整数二分：
bool check(int x) {/* ... */} // 检查x是否满足某种性质 //以下为y总总结的两个代码模板，可选择任何一个进行记忆，注意区别两个代码的不同 //背下下来拿任何一个就足够了； int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; //等同于 mid = (l + r) / 2; 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; //如果更新为 l = mid，则上一行需要补上+ 1，即mid = l + r + 1 >> 1 //如果更新如 bsearch_1 中的r = mid则不需要补 + 1 //具体原因y总上课有将，没有太理解什么意思，索性不求甚解 //这里可以先记住 是否补充 + 1取决于更新后是r = mid还是l = mid，后者需要补 + 1 //具体为什么需要补充 + 1，后续理解了会更新说明。 else r = mid - 1; } return l; }
2.浮点数二分模板：
bool check(double x) {/* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { const double eps = 1e-8; // eps 表示精度，取决于题目对精度的要求（要比题目要求的高2个精度） while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
四、时间复杂度的分析：
博主自己还没搞懂，先鸽了，日后一定补齐时间复杂度和证明。
