c++ 二分查找

二分法(Binary Search)是一种高效的查找算法,它在有序数组中查找一个元素,利用分治法的思想将查找空间逐步缩小一半。二分法的时间复杂度是 O(log n),比起线性查找(O(n))要高效得多。

基本思想

  1. 首先确定一个范围(通常是数组的左右边界)。
  2. 计算范围的中间位置。
  3. 如果中间位置的元素是目标元素,则返回该位置。
  4. 如果中间位置的元素大于目标元素,则将搜索范围缩小为中间元素左侧的部分。
  5. 如果中间位置的元素小于目标元素,则将搜索范围缩小为中间元素右侧的部分。
  6. 重复这个过程直到找到目标元素或者搜索区间为空。

代码实现

普通二分查找

#include <iostream>
#include <vector>
using namespace std;int binarySearch(const vector<int>& arr, int target) {int left = 0, right = arr.size() - 1;while (left <= right) {// int mid = left + (right - left) / 2;  // 防止溢出int mid = (left + right) >> 1;if (arr[mid] == target) {return mid;  // 找到目标,返回索引}else if (arr[mid] < target) {left = mid + 1;  // 目标在右边}else {right = mid - 1;  // 目标在左边}}return -1;  // 如果没有找到目标,返回-1
}int main() {vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};int target = 7;int index = binarySearch(arr, target);if (-1 != index) {cout << "元素 " << target << " 在数组中的位置是: " << index << endl;} else {cout << "元素 " << target << " 不在数组中。" << endl;}return 0;
}

查找插入位置

在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

// leetcode --- 35. 搜索插入位置
int searchInsert(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;int ans = nums.size();while (l <= r) {int mid = (l + r) >> 1;if (nums[mid] < target) {l = mid + 1;} else {r = mid - 1;ans = mid;}}return ans;
}

应用

查找目标值的最左位置(查找重复元素的第一个位置)

当数组中有重复元素时,二分查找可以用来找到目标值的第一个出现位置。

问题描述:

给定一个升序排列的数组 arr 和一个目标值 target,请找出 target 在数组中首次出现的位置。

#include <iostream>
#include <vector>
using namespace std;int binarySearchLeft(const vector<int>& arr, int target) {int left = 0, right = arr.size();while (left < right) {int mid = left + (right - left) / 2;// 如果当前值等于目标值,则向左侧继续查找if (arr[mid] >= target) {right = mid;} else {left = mid + 1;}}// 检查 left 是否越界或值是否等于目标if (left < arr.size() && arr[left] == target) {return left;}return -1;  // 未找到目标值
}int main() {vector<int> arr = {1, 2, 2, 2, 3, 4, 5};int target = 2;int index = binarySearchLeft(arr, target);if (index != -1) {cout << "目标值 " << target << " 首次出现在索引: " << index << endl;} else {cout << "目标值 " << target << " 不在数组中。" << endl;}return 0;
}

查找目标值的最右位置(查找重复元素的最后位置)

类似于查找最左位置,我们也可以通过二分查找来找到目标值的最后一个出现位置。

问题描述:

给定一个升序排列的数组 arr 和一个目标值 target,请找出 target 在数组中最后出现的位置。

#include <iostream>
#include <vector>
using namespace std;int binarySearchRight(const vector<int>& arr, int target) {int left = 0, right = arr.size();while (left < right) {int mid = left + (right - left) / 2;// 如果当前值等于目标值,则向右侧继续查找if (arr[mid] <= target) {left = mid + 1;} else {right = mid;}}// 检查 left 是否越界或值是否等于目标if (left - 1 >= 0 && arr[left - 1] == target) {return left - 1;}return -1;  // 未找到目标值
}int main() {vector<int> arr = {1, 2, 2, 2, 3, 4, 5};int target = 2;int index = binarySearchRight(arr, target);if (index != -1) {cout << "目标值 " << target << " 最后出现在索引: " << index << endl;} else {cout << "目标值 " << target << " 不在数组中。" << endl;}return 0;
}

查找最小的满足条件的数

有时我们需要找到某个最小的满足特定条件的数,这通常使用二分查找来优化。例如,找出第一个大于等于某个值的元素。

问题描述:

给定一个升序数组 arr 和一个目标值 target,找到第一个大于等于 target 的元素。如果没有找到,则返回 -1。

#include <iostream>
#include <vector>
using namespace std;int binarySearchLowerBound(const vector<int>& arr, int target) {int left = 0, right = arr.size();while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] < target) {left = mid + 1;  // 搜索右边} else {right = mid;  // 搜索左边}}// 检查是否越界if (left < arr.size() && arr[left] >= target) {return left;}return -1;  // 没有找到满足条件的元素
}int main() {vector<int> arr = {1, 2, 4, 6, 8, 10};int target = 5;int index = binarySearchLowerBound(arr, target);if (index != -1) {cout << "第一个大于等于 " << target << " 的元素在索引: " << index << ", 值为 " << arr[index] << endl;} else {cout << "没有找到满足条件的元素。" << endl;}return 0;
}

求解旋转排序数组中的目标值

有时数组可能已经进行了旋转(比如,排序数组 arr = [4, 5, 6, 7, 0, 1, 2]),我们可以使用二分查找来找到目标值的位置。

问题描述:

给定一个旋转过的升序数组 arr 和一个目标值 target,请找出目标值在数组中的索引。如果不存在,返回 -1。

#include <iostream>
#include <vector>
using namespace std;int searchRotatedArray(const vector<int>& arr, int target) {int left = 0, right = arr.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;  // 找到目标值}// 判断左边是否有序if (arr[left] <= arr[mid]) {if (arr[left] <= target && target < arr[mid]) {right = mid - 1;  // 目标在左边} else {left = mid + 1;  // 目标在右边}} else {// 右边有序if (arr[mid] < target && target <= arr[right]) {left = mid + 1;  // 目标在右边} else {right = mid - 1;  // 目标在左边}}}return -1;  // 未找到目标值
}int main() {vector<int> arr = {6, 7, 9, 15, 19, 2, 3};int target = 3;int index = searchRotatedArray(arr, target);if (index != -1) {cout << "目标值 " << target << " 在数组中的索引是: " << index << endl;} else {cout << "目标值 " << target << " 不在数组中。" << endl;}return 0;
}

总结

  • 时间复杂度:无论是普通的二分查找还是查找插入位置,时间复杂度都是 O(log n),其中 n 是数组的大小。

  • 适用场景:二分查找仅适用于有序数组。如果数组是无序的,必须先对其进行排序才能使用二分法。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

SE30 程序运行时间评估

日常执行报表的时候 可能会遇到报表反应时间太长 用户无法接受的情况&#xff0c;此时 作为IT同事 需要分析程序的运行时间&#xff0c;可以使用SAP标准事务码SE30. 1、选择运行时分析-测量-立即执行&#xff08;有些程序可能没有此按钮 需联系开发增加&#xff09; 2、以发…

T-Rex Label标注

这个是做大量数据集的时候用到的&#xff0c;但我觉得他比labelimg好用。 仙人指路✈trexlabel 基本标注 如果是从新开始的话就是 导入图片然后进行直接标注 如果是后期添加图片继续标注&#xff0c;选择你需要的数据集格式&#xff0c;导入即可。 如此&#xff0c;进去就…

部署zabbix遇到问题: cannot find a valid baseurl for repo:centos-sclo-rh/x86 64 怎么解决 ?

安装 Zabbix 前端包&#xff0c;提示cannot find a valid baseurl for repo&#xff1a;centos-sclo-rh/x86 64 安装zabbix前端包 # yum install zabbix-web-mysql-scl zabbix-apache-conf-scl 解决办法&#xff1a; 原因是&#xff1a;CentOS7的SCL源在2024年6月30日停止维护…

小程序+公众号统一账号unionid,实现pc+公众号+小程序统一身份

一、微信开放平台 注册开发者账号、绑定公众号、小程序 二、小程序端获取unionid 1获取code wx.login({success: res > {console.log("getCode", res.code)this.getOpenId(res.code)}}) 2通过code调用后台方法获取openid,unionid 小程序端 getOpenId: functi…

LeetCode【0037】解数独

本文目录 1 中文题目2 求解方法&#xff1a;递归回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目 编写一个程序&#xff0c;通过填充空格来解决数独问题。数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只…

零碎02-接口文档管理

目录 一、背景故事 二、解决方案分析 1. 静态文档方案 2. Swagger Springfox 3. Knife4j增强方案 三、示例 1. 添加依赖 2. 配置Knife4j 3. 创建knife4j配置类 4. 启动Spring Boot项目并访问接口文档 5. 使用示例 6. 测试和使用 四、总结 一、背景故事 酷乐是一名…

指标体系构建:如何设计北极星指标设计?

目录 1 北极星指标的作用 2 北极星指标设计标准 标准1 标准2 标准3 标准4 标准5 标准6 3 小结 1 北极星指标的作用 北极星指标是公司业务成功的关键指标&#xff0c;反映了公司为用户带来的价值&#xff0c;有以下3点作用&#xff1a; ● 像北极星一样&#xff0c…

三菱FX5UPLC以太网Socket通信功能Passive开放的程序示例

Passive开放的通信流程如下所示。 参数设置 示例程序中使用的参数设置如下所示。 [CPU模块】 导航窗口↔[参数]↔[模块型号]↔[模块参数]-[以太网端口]-[基本设置]-[对象设备连接配置设置]↔[详细设置]→[以太网配置(内置以太网端口)]画面 【以太网模块】 [导航]中「参数]→[模…

【MATLAB源码-第292期】基于matlab的4ASK调制解调窄带通信系统仿真,输出各节点波形图以及误码率曲线图。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 窄带通信系统是指带宽较小、频谱利用效率较低的通信系统。与宽带通信系统相比&#xff0c;窄带系统的特点是信号的带宽相对较窄&#xff0c;因此需要更精确的调制技术来实现有效的通信。在窄带通信中&#xff0c;常见的调制方…

【搜索结构】AVL树的学习与实现

目录 什么是AVL树 AVL树的定义 插入函数的实现 左单旋和右单旋 左右双旋与右左双旋 什么是AVL树 AVL树实际上就是二叉搜索树的一种变体&#xff0c;我们都知道二i叉搜索树可以将查找的时间复杂度提升到O(logn)&#xff0c;极大提升搜索效率。但是在极端情况下&#xff0c;当…

【专题】2024年中国消费者消费意愿调查报告汇总PDF洞察(附原数据表)

原文链接&#xff1a;https://tecdat.cn/?p38242 当今时代&#xff0c;经济社会多元发展&#xff0c;消费市场复杂多变。消费者的行为、需求和支出意愿不断演变&#xff0c;深刻影响着各个领域的发展。家庭余钱的用途反映出消费者在储蓄、教育、医疗等方面的考量。在消费领域…

推荐一款游戏玩家性能优化工具:Razer Cortex

Razer Cortex是一款专为游戏玩家设计的性能优化工具&#xff0c;它旨在提升玩家的游戏体验。通过该软件&#xff0c;用户可以优化 PC 性能&#xff0c;从而提高游戏的流畅度&#xff0c;减少延迟并增强视觉效果&#xff0c;尤其在需要精准操作的游戏中&#xff0c;流畅的画面和…

人工智能(AI)对于电商行业的变革和意义

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/402a907e12694df5a34f8f266385f3d2.png#pic_center> &#x1f393;作者简介&#xff1a;全栈领域优质创作者 &#x1f310;个人主页&#xff1a;百锦再新空间代码工作室 &#x1f4de;工作室&#xff1a;新空间代…

1435:【例题3】曲线 一本通 代替三分

1435&#xff1a;【例题3】曲线 题目来源&#xff1a;一本通oj链接 代替三分 题意 给出t组数据&#xff0c;每组里面有n个函数&#xff0c;求出t组数据的函数的最小值 思路 函数是二次函数&#xff0c;具有单峰性&#xff0c;利用左右两边单调性的原理可以进行答案三分处…

英伟达Isaac Manipulator产品体验

相关配置 Isaac Manipulator3.1.0Isaac Sim4.2.0Ubuntu20.04GPURTX 4090 LaptopCPUI9 13900HXMem64GB 过程记录与反馈 GPU加速效果 请描述您在使用Isaac Manipulator时&#xff0c;调用cuMotion加速库来进行机器人运动规划和轨迹优化等任务的步骤和过程&#xff0c;并记录任…

“非法”操控lambda(python)

能过python解释器关卡即是合法脚本代码&#xff0c;偶尔的“违规”操控也是一种唯美。 (笔记模板由python脚本于2024年11月13日 11:18:21创建&#xff0c;本篇笔记适合熟悉python的lambda操控的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.pyth…

[ 网络安全介绍 5 ] 为什么要学习网络安全?

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…

java八股笔记-1-java基础

java 特点&#xff1a; 1.平台无关性&#xff0c;java 的字节码文件可以在任何安装了 JVM 的系统上运行 2.面相对象&#xff0c;几乎一切都可以抽象为对象&#xff0c;包括类&#xff0c;对象&#xff0c;继承&#xff0c;封装&#xff0c;多态&#xff0c;抽象 抽象&#xf…

Java入门16——接口

我们今天来学习接口&#xff0c;和继承有点像&#xff0c;话不多说&#xff0c;开始正题~ 一、接口 1.为什么要用接口 接口其实和继承很像&#xff0c;但是继承是 is-a 的关系&#xff0c;接口是 has-a 的关系&#xff0c;而且继承只能是一对一的关系&#xff0c;但是接口可以…

Sigrity SPEED2000 Power Ground Noise Simulation模式如何进行串扰分析操作指导-trace耦合

Sigrity SPEED2000 Power Ground Noise Simulation模式如何进行串扰分析操作指导-trace 耦合 Sigrity Power SI Power Ground Noise Simulation模式可以用来分析信号间的串扰,以下图为例 2D视图