C++算法学习2:二分算法精讲

一、实数二分法回顾

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的位置

问题要求

  1. 输入无序数组

  2. 输出首次出现3的位置(从1开始计数)

  3. 不存在时输出-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;
}

关键点解析

  1. 结构体排序:保存原始位置信息

  2. 查找策略

    • 查找第一个≥3的元素

    • 反向扫描确认首次出现位置

  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_boundupper_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

五、二分算法适用场景

  1. 有序数据集:单调递增/递减序列

  2. 离散数值查找:整数集合中的定位

  3. 分治问题:最大值最小化/最小值最大化问题

  4. 高效查询:时间复杂度O(log n)


六、常见错误及规避

  1. 死循环问题

    • 确保区间更新有进展

    • 使用标准模板:left = mid + 1 / right = mid - 1

  2. 整数溢出

    int mid = left + (right - left) / 2;  // 正确写法
  3. 边界处理

    • 初始化时明确开闭区间

    • 终止条件验证 left <= right


通过系统掌握实数与整数二分法的实现差异,结合经典应用场景的实战训练,可显著提升算法设计能力与代码实现水平。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33826.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

手写一个简易版的tomcat

Tomcat 是一个广泛使用的开源 Servlet 容器&#xff0c;用于运行 Java Web 应用程序。深入理解 Tomcat 的工作原理对于 Java 开发者来说是非常有价值的。本文将带领大家手动实现一个简易版的 Tomcat&#xff0c;通过这个过程&#xff0c;我们可以更清晰地了解 Tomcat 是如何处理…

object.assign和扩展运算法是深拷贝还是浅拷贝,两者区别

object.assign和扩展运算法是深拷贝还是浅拷贝&#xff0c;两者区别 1. 浅拷贝的本质2. Object.assign 和扩展运算符的区别‌3. 具体场景对比‌合并多个对象‌‌复制数组‌‌处理默认值‌ ‌4. 如何实现深拷贝&#xff1f;JSON.parse(JSON.stringify(obj))‌‌递归深拷贝函数第…

X-CLIP和X-FLORENCE论文解读

1.研究背景 尽管已有研究探索了如何将语言-图像模型迁移到其他下游任务&#xff08;如点云理解和密集预测&#xff09;&#xff0c;但视频识别领域的迁移和适应性研究还不够充分。例如&#xff0c;ActionCLIP提出了一种“预训练、提示和微调”的框架用于动作识别&#xff0c;但…

微信小程序刷题逻辑实现:技术揭秘与实践分享

页面展示&#xff1a; 概述 在当今数字化学习的浪潮中&#xff0c;微信小程序以其便捷性和实用性&#xff0c;成为了众多学习者刷题备考的得力工具。今天&#xff0c;我们就来深入剖析一个微信小程序刷题功能的实现逻辑&#xff0c;从代码层面揭开其神秘面纱。 小程序界面布局…

Android UI 组件系列(二):Button 进阶用法

引言 在上一篇博客中&#xff0c;我们介绍了 Button 的基本用法和常见属性&#xff0c;掌握了 Button 的基础知识。然而&#xff0c;在实际开发中&#xff0c;Button 远不止于简单的点击功能&#xff0c;它还可以支持不同的变体、丰富的自定义样式&#xff0c;以及更灵活的状态…

【云馨AI-大模型】RAGFlow功能预览:Dify接入外部知识库RAGFlow指南

介绍 Dify介绍 开源的 LLM 应用开发平台。提供从 Agent 构建到 AI workflow 编排、RAG 检索、模型管理等能力&#xff0c;轻松构建和运营生成式 AI 原生应用。比 LangChain 更易用。官网&#xff1a;https://dify.ai/zh RAGFlow介绍 RAGFlow 是一款基于深度文档理解构建的…

Redis超高并发分key实现

Redis扛并发的能力是非常强的&#xff0c;所以高并发场景下经常会使用Redis&#xff0c;但是Redis单分片的写入瓶颈在2w左右&#xff0c;读瓶颈在10w左右&#xff0c;如果在超高并发下即使是集群部署Redis&#xff0c;单分片的Redis也是有可能扛不住的&#xff0c;如下图所示&a…

缓存使用的具体场景有哪些?缓存的一致性问题如何解决?缓存使用常见问题有哪些?

缓存使用场景、一致性及常见问题解析 一、缓存的核心使用场景 1. 高频读、低频写场景 典型场景&#xff1a;商品详情页、新闻资讯、用户基本信息。特点&#xff1a;数据更新频率低&#xff0c;但访问量极高。策略&#xff1a; Cache-Aside&#xff08;旁路缓存&#xff09;&a…

HTML5(Web前端开发笔记第一期)

p.s.这是萌新自己自学总结的笔记&#xff0c;如果想学习得更透彻的话还是请去看大佬的讲解 目录 三件套标签标题标签段落标签文本格式化标签图像标签超链接标签锚点链接默认链接地址 音频标签视频标签 HTML基本骨架综合案例->个人简介列表表格表单input标签单选框radio上传…

ubuntu22.04 关于挂在设备为nfts文件格式无法创建软连接的问题

最近遇到情况&#xff0c;解压工程报错&#xff0c;无法创建软连接 但是盘内还有130G空间&#xff0c;明显不是空间问题&#xff0c;查找之后发现是移动硬盘的文件格式是NTFS&#xff0c;在ubuntu上不好兼容&#xff0c;于是报错。 开贴记录解决方案。 1.确定文件格式 使用命…

深度解读DeepSeek部署使用安全(48页PPT)(文末有下载方式)

深度解读DeepSeek&#xff1a;部署、使用与安全 详细资料请看本解读文章的最后内容。 引言 DeepSeek作为一款先进的人工智能模型&#xff0c;其部署、使用与安全性是用户最为关注的三大核心问题。本文将从本地化部署、使用方法与技巧、以及安全性三个方面&#xff0c;对Deep…

RK3568 Android13 源码编译

提示&#xff1a;RK3568 Android13 源码编译 脚本&#xff0c;源码编译管理方式优化 文章目录 获取源码设置屏幕配置确认屏幕修改源码的设备树 修改线程数整体编译Android固件配置JDK java 环境 source javaenv.sh使能编译 build/envsetup.sh lunch topeet_rk3568-userdebug整体…

【CentOS】搭建Radius服务器

目录 背景简介&#xff1a;Radius是什么&#xff1f;Radius服务器验证原理搭建Radius服务器环境信息yum在线安装配置FreeRADIUS相关文件clients.conf文件users文件重启服务 验证 参考链接 背景 在项目中需要用到Radius服务器作为数据库代理用户的外部验证服务器&#xff0c;做…

ToB公司找客户专用|大数据获客系统

对于ToB公司而言&#xff0c;找到并吸引合适的潜在客户并非易事。传统的获客手段如参加行业展会、电话推销以及直接拜访等&#xff0c;虽然在过去取得了一定成效&#xff0c;但如今却暴露出诸多问题。首先&#xff0c;这些方法往往成本高昂&#xff0c;无论是时间还是金钱上的投…

Linux 文件权限类

目录 文件属性 从左到右的10个字符表示 rwx作用文件和目录的不同解释 图标&#xff1a; 案例实操 chmod 改变权限 基本语法 经验技巧 案例实操 拓展&#xff1a;可以通过一个命令查看用户列表 chown改变所有者 基本语法 选项说明 案例实操 chgrp 改变所属组 基…

DeepSeek技术解析:MoE架构实现与代码实战

以下是一篇结合DeepSeek技术解析与代码示例的技术文章&#xff0c;重点展示其核心算法实现与落地应用&#xff1a; DeepSeek技术解析&#xff1a;MoE架构实现与代码实战 作为中国AI领域的创新代表&#xff0c;DeepSeek在混合专家模型&#xff08;Mixture of Experts, MoE&…

vue3:八、登录界面实现-页面初始搭建、基础实现

一、初始工作 1、创建登录文件 在src/views中创建文件LoginView.vue文件 2、创建路由 在router/index.js中增加登录的信息 代码 import { createRouter, createWebHistory } from vue-router import HomeView from ../views/HomeView.vue const router createRouter({hist…

dify+mysql的诗词助手

目录 数据库表结构&#xff1a; 数据库查询的http服务搭建&#xff1a; 流程引擎搭建&#xff1a; 开始&#xff0c; HTTP查询数据库&#xff0c; LLM数据分析&#xff0c; 直接回复&#xff0c; 效果测试&#xff1a; 下载链接&#xff1a; 数据库表结构&#xff1a;…

jenkins 配置邮件问题整理

版本&#xff1a;Jenkins 2.492.1 插件&#xff1a; A.jenkins自带的&#xff0c; B.安装功能强大的插件 配置流程&#xff1a; 1. jenkins->系统配置->Jenkins Location 此处的”系统管理员邮件地址“&#xff0c;是配置之后发件人的email。 2.配置系统自带的邮件A…

谷歌Chrome或微软Edge浏览器修改网页任意内容

在谷歌或微软浏览器按F12&#xff0c;打开开发者工具&#xff0c;切换到console选项卡&#xff1a; 在下面的输入行输入下面的命令回车&#xff1a; document.body.contentEditable"true"效果如下&#xff1a;