当前位置: 首页 > news >正文

C++ 算法——二分查找

如果要你在一个升序序列中查找一个值的位置,你是否还会傻乎乎的用下面这个 O ( n ) \mathcal O(n) O(n) 的代码暴力查找,如果是,我告诉你,其实根本不用这么做。

int find(int a[],int n,int k) {for(int i=0;i<n;++i) if(a[i]==k) return i;
}

猜数字这个游戏大家都玩过吧,这里介绍以下规则:

  1. 一名玩家在一个范围内想出一个数。
  2. 这名玩家告诉其他玩家他所想的范围。
  3. 其他玩家在这个范围内猜数,若:
    • 猜中了:该玩家获胜
    • 没猜中:根据该玩家猜的数缩小范围,然后接着进行操作 2。对于缩小范围,设初始范围为 l ∼ y l\sim y ly,要猜的数为 n n n,猜的数位 n n n,若:
      • m < n m<n m<n,将范围缩小至 m ∼ r m\sim r mr
      • m > n m>n m>n,将范围缩小至 l ∼ m l\sim m lm

显然,想要最快猜到该数,就需要采用折半的方法去猜,每次都猜这个范围的中间数。二分查找也是一样,对于每一次查找,都判断中间的数与要找的数的大小关系,然后采取对应的操作。

需要注意的是,二分查找需要保证序列是升序的。

这里放个代码:

//循环版
int find(int a[],int n,int k) {int l=0,r=n-1;while(l<=r) {int mid=(l+r)/2;if(a[mid]>k) r=mid-1;else if(a[mid]<k) l=mid+1;else if(a[mid]==k) return mid;}return -1;
}
//递归版
int find(int a[],int n,int k,int l,int r) {if(l>r) return -1;int mid=(l+r)/2;if(a[mid]>k) return find(a,n,k,l,mid-1);else if(a[mid]<k) return find(a,n,k,mid+1,r);else if(a[mid]==k) return mid;
}

练习题:洛谷 link

http://www.lryc.cn/news/395898.html

相关文章:

  • 【自动驾驶仿真在做什么——初学者总结(陆续补充)】
  • 探索HTML5的设计原则:引领Web开发的未来方向
  • 力扣喜刷刷--day1
  • 配置linux的yum镜像为阿里镜像源
  • react使用markdown进行展示
  • 实时温湿度监测系统:Micropython编码ESP32与DHT22模块的无线数据传输与PC端接收项目
  • CloudWatch Logs Insights 详解
  • Jmeter在信息头中设置Bearer与 token 的拼接值
  • C#程序调用Sql Server存储过程异常处理:调用存储过程后不返回、不抛异常的解决方案
  • 数据统计与数据分组18-25题(30 天 Pandas 挑战)
  • Apache Seata应用侧启动过程剖析——注册中心与配置中心模块
  • 大话光学原理:1.“实体泛光说”、反射与折射
  • 住宅代理、移动代理和数据中心代理之间的区别
  • 光学传感器图像处理流程(一)
  • el-table 树状表格查询符合条件的数据
  • MQTT教程--服务器使用EMQX和客户端使用MQTTX
  • 326. 3 的幂
  • 多标签问题
  • suricata7 rule加载(三)加载options
  • 【电路笔记】-C类放大器
  • c++语法之函数重载
  • EtherCAT主站IGH-- 11 -- IGH之fmmu_config.h/c文件解析
  • 如何使用IDEA快速清理无效代码(荣耀典藏版)
  • ELK优化之Filebeat部署
  • 蝙蝠优化算法(Bat Algorithm,BA)及其Python和MATLAB实现
  • vscode运行java中文乱码,引发的mac配置问题
  • MySQL之备份与恢复(五)
  • 离线运行Llama3:本地部署终极指南_liama2 本地部署
  • 【YOLO8系列】(二)YOLOv8环境配置,手把手嘴对嘴保姆教学
  • MFC常见问题解决