一、实数二分法回顾
1.1问题背景
在1~2的范围内找到一个x,使得式子5x2 -9x +1 的绝对值<10-9(即无限接近0) 要求:x精确到小数点后9位。
换句话说也就是求:就是求方程 5x2- 9x + 1 =0 在1~2内的近似解
1.2怎么找到这个x呢?
我们需要一个一个试,关键是:试哪些数?
先试边界1和2
将1、2分别带入下列方程
令y = 5x2 - 9x + 1 ,目标:|y| <10-9
得到y=-3、y=3
下一个试谁呢?
将x=1.5带入y = 5x2 - 9x + 1
1.3接下来我们往左边试还是往右边试?
应该往右试:
我们接下来要做的就是反复的左右试题x的值,直到y的绝对值小于10的-9次方为止。
1.4 算法实现
#include <iostream> #include <cmath> #include <iomanip> using namespace std;int main() {double left = 1, right = 2;double x = (left + right) / 2;double y = 5 * x * x - 9 * x + 1;while (abs(y) > 1e-9) {if (y > 0) right = x; // 解在左侧else left = x; // 解在右侧x = (left + right) / 2;y = 5 * x * x - 9 * x + 1;}cout << fixed << setprecision(9) << x;return 0; }
核心特点
-
终止条件:解的精度达到
1e-9
-
区间更新:直接赋值
left = x
或right = x
-
中间值计算:无需考虑整数溢出问题
二、整数二分法解析
猜数字游戏
输入一个范围在 [1, 1000]
内的数字,让计算机去猜,看使用二分法,计算机需要几次就能猜出来:
#include<iostream> using namespace std; int main(){int sum=0;//记录一共猜了几次数 int b=0,e=1000,x=173;//b,e左边界和右边界确定了数据范围,x=173是我们猜的数字 //使用二分法开始猜数 while(b<=e){//左边界小于等于右边界是整数二分的条件 int mid=(b+e)/2;//获取中间值 if(x==mid){cout<<"猜对了"<<endl;break;}else if(mid>x){cout<<"大了"<<mid<<endl; e=mid-1;//更新右边界值 sum++;}else{cout<<"小了"<<mid<<endl; b=mid+1;//更新左边界值 sum++;}}cout<<"一共猜了几次"<<sum; return 0; }
与实数二分的核心差异
特性 | 实数二分 | 整数二分 |
---|---|---|
终止条件 | 精度达到阈值 | left > right |
中间值计算 | 直接取平均 | 需要处理整数除法特性 |
区间更新 | 直接赋值 | 需要±1操作 |
内存消耗 | 浮点运算 | 整型运算 |
三、整数二分经典应用
练习:在数组中查找数字3的位置
问题要求:
-
输入无序数组
-
输出首次出现3的位置(从1开始计数)
-
不存在时输出-1
实现方案
#include <iostream> #include <algorithm> using namespace std;struct Item {int id;int value; } a[100];bool cmp(Item a, Item b) {return a.value < b.value; }int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) {a[i].id = i;cin >> a[i].value;}// 排序保持原始位置sort(a + 1, a + n + 1, cmp);// 二分查找int left = 1, right = n, res = -1;while (left <= right) {int mid = left + (right - left) / 2;if (a[mid].value >= 3) {if (a[mid].value == 3) res = a[mid].id;right = mid - 1;} else {left = mid + 1;}}// 验证是否为首次出现if (res != -1) {for (int i = right + 1; i <= left; ++i) {if (a[i].value == 3) {res = min(res, a[i].id);}}}cout << (res != -1 ? res : -1);return 0; }
关键点解析
-
结构体排序:保存原始位置信息
-
查找策略:
-
查找第一个≥3的元素
-
反向扫描确认首次出现位置
-
-
边界处理:处理多个相同值的情况
四、c++标准库二分函数解析
1. lower_bound 函数
功能描述
在有序区间中查找第一个大于或等于目标值的元素位置
使用模板
// 函数原型 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);// 示例代码 int a[] = {4,6,1,7,9,6,5,12,15,8}; sort(a, a+10); // {1,4,5,6,6,7,8,9,12,15}int target = 11; auto it = lower_bound(a, a+10, target); int pos = it - a; // 计算索引位置if(pos < 10) {cout << "找到的数是:" << *it << " 位置是:" << pos; // 输出:12 位置8 } else {cout << "未找到"; }
特性说明
-
时间复杂度:O(log n)
-
前提条件:区间必须已排序
-
返回值:若找到返回对应迭代器,否则返回
last
2. upper_bound 函数
功能描述
在有序区间中查找第一个严格大于目标值的元素位置
使用对比
int a[] = {1,2,2,3,3,3,4,5}; int n = sizeof(a)/sizeof(int);int val = 3; auto lb = lower_bound(a, a+n, val); // 指向第一个3(索引3) auto ub = upper_bound(a, a+n, val); // 指向第一个4(索引6)cout << "元素3的个数:" << ub - lb; // 输出3
3. 函数对比表
特性 | lower_bound | upper_bound |
---|---|---|
查找条件 | ≥ target | > target |
返回值位置 | 第一个可插入位置(保序) | 最后可插入位置(保序) |
常见用途 | 查找元素是否存在 | 统计元素出现次数 |
未找到返回值 | 指向第一个>target的元素 | 指向最后一个元素的下一个位置 |
五、综合应用实例
案例:求解三次方程近似根
double cube_root(double L, double R) {const double eps = 1e-12;while (R - L > eps) {double mid = (L + R) / 2;if (mid*mid*mid > 27) { // 求³√27的近似值R = mid;} else {L = mid;}}return L; }// 输出:3.000000000000
五、二分算法适用场景
-
有序数据集:单调递增/递减序列
-
离散数值查找:整数集合中的定位
-
分治问题:最大值最小化/最小值最大化问题
-
高效查询:时间复杂度O(log n)
六、常见错误及规避
-
死循环问题:
-
确保区间更新有进展
-
使用标准模板:
left = mid + 1
/right = mid - 1
-
-
整数溢出:
int mid = left + (right - left) / 2; // 正确写法
-
边界处理:
-
初始化时明确开闭区间
-
终止条件验证
left <= right
-
通过系统掌握实数与整数二分法的实现差异,结合经典应用场景的实战训练,可显著提升算法设计能力与代码实现水平。