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

数据结构——二分查找法

二分查找法(Binary Search)是一种高效的查找算法,通常用于在已排序的数组或列表中查找特定的目标值。这个算法的基本思想是不断将查找范围缩小为原来的一半,直到找到目标值或确定目标值不存在。

二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时,都应该考虑二分查找。如果集合是无序的,我们可以总是在应用二分查找之前先对其进行排序。

二分查找一般由三个主要部分组成:
1.预处理一如果集合未排序,则进行排序.
2.二分查找一 使用循环或递归在每次比较后将查找空间划分为两半
3. 后处理在剩余空间中确定可行的候选者

1.二分查找函数 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板

int binarySearch(const std::vector<int>& arr, int target) {int left = 0;int right = arr.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标值,返回其索引}else if (arr[mid] < target) {left = mid + 1; // 目标值在右半部分}else {right = mid - 1; // 目标值在左半部分}}return -1; // 目标值不存在
}

2.二分查找函数 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

int binarySearch(vector<int>& nums, int target) {if (nums.size() == 0)return -1;int left = 0, right = nums.size();while (left < right) {// Prevent (left + right) overflowint mid = left + (right - left) / 2;if (nums[mid] == target){ return mid;}else if (nums[mid] < target) { left = mid + 1; }else { right = mid; }}// Post-processing:// End Condition: left == rightif (left != nums.size() && nums[left] == target) return left;return -1;
}

3.二分查找函数 是二分查找的另一种独特形式。 它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

int binarySearch3(vector<int>& nums, int target) {if (nums.size() == 0)return -1;int left = 0, right = nums.size() - 1;while (left + 1 < right) {// Prevent (left + right) overflowint mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}else if (nums[mid] < target){left = mid;}else{right = mid;}}// Post-processing:// End Condition: left + 1 == rightif (nums[left] == target)return left;if (nums[right] == target)return right;return -1;
}

相关文章:

数据结构——二分查找法

二分查找法&#xff08;Binary Search&#xff09;是一种高效的查找算法&#xff0c;通常用于在已排序的数组或列表中查找特定的目标值。这个算法的基本思想是不断将查找范围缩小为原来的一半&#xff0c;直到找到目标值或确定目标值不存在。 二分查找是一种在每次比较之后将查…...

服务端渲染(SSR):提升Web应用性能和用户体验的关键技术

&#x1f482; 个人网站:【工具大全】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 引言 服务端渲染&#…...

如何工作和生活相平衡?

之前待过一家外企&#xff0c;他们的口号是 Balancing work and life&#xff0c;工作和生活相平衡。辗转几家公司之后&#xff0c;发现这个越来越难了&#xff0c;越来越少的时间投入家庭和自己的生活。 人生的意义 &#xff08;AI&#xff09; 人生的意义是一个深奥而复杂的…...

semaphere部署,配置ldap

在处理 Ansible 相关项目时&#xff0c;我们经常面临繁琐的命令行操作&#xff0c;这对于不熟悉命令行的用户来说可能是一个挑战。此外&#xff0c;当项目规模扩大时&#xff0c;跟踪和管理多个 playbook 变得困难&#xff0c;同时缺乏对失败的及时通知和访问控制。这些问题催生…...

Java 泛型 T,E,K,V,?

泛型带来的好处 在没有泛型的情况的下&#xff0c;通过对类型 Object 的引用来实现参数的“任意化”&#xff0c;“任意化”带来的缺点是要做显式的强制类型转换&#xff0c;而这种转换是要求开发者对实际参数类型可以预知的情况下进行的。对于强制类型转换错误的情况&#xf…...

软件测试技术之地图导航的测试用例

外观测试 屏幕显示不能有花屏、黑点和闪屏&#xff0c;清晰度、亮度、颜色要正常。 检测所有按键都能起到相应作用&#xff0c;是否手感不良。 UI显示状态、颜色、清晰度、效果。 控制&#xff1a;放大&#xff0c;缩小&#xff0c;音量调节功能测试。 交叉路口查询测试&am…...

【C++】常用集合算法

0.前言 1.set_intersection #include <iostream> using namespace std;// 常用集合算法 交集set_intersection #include<vector> #include<algorithm>void myPrint(int val) {cout << val << " "; }void test01() {vector<int>v…...

css flex:1;详解,配合demo效果解答

前言 给设置了display&#xff1a;flex的子组件设置了flex&#xff1a;1&#xff1b;就能让他填满整个容器&#xff0c;如果有多个就平均 flex&#xff1a;1&#xff1b;是另外三个样式属性的简写&#xff0c;等同 flex-grow: 0; flex-shrink: 1; flex-basis: auto;我们就针…...

discuzQ安装

我们开始配置php,安装两个扩展。 在宝塔面板中&#xff0c;单击软件商城->已安装&#xff0c;查找已安装的 PHP 软件。 然后在 php 管理中&#xff0c;单击禁用函数&#xff0c;进入设置页面。 在列表中单击删除函数 putenv、readlink、symlink、shell_exec &#xff0c;…...

深入解析NLP情感分析技术:从篇章到属性

目录 1. 情感分析概述1.1 什么是情感分析&#xff1f;- 情感分析的定义- 情感分析的应用领域 1.2 为什么情感分析如此重要&#xff1f;- 企业和研究的应用- 社交媒体和公共意见的影响 2. 篇章级情感分析2.1 技术概览- 文本分类的基本概念- 机器学习与深度学习方法- 词嵌入的力量…...

JVM的双亲委派模型

定义与本质&#xff1a; 类加载器用来把类文件加载到JVM内存中。从JDK1.2开始&#xff0c;类加载过程采用双亲委派模型&#xff0c;保证Java平台安全。 父类委托的定义&#xff1a; 一个类加载器在接到加载类请求的时候&#xff0c;首先不会去加载这个类&#xff0c;而是把这个…...

js中如何判断一个变量是否为数字类型?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐使用Number.isNaN()方法⭐使用正则表达式⭐使用isNaN()函数⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个…...

使用阿里PAI DSW部署Stable Diffusion WebUI

进入到网址https://pai.console.aliyun.com/里边。 点击创建实例。 把实例名称填写好&#xff0c;选择GPU规格&#xff0c;然后选择实例名称是ecs.gn6v-c8g1.2xlarge。 选择stable-diffusion-webui-env:pytorch1.13-gpu-py310-cu117-ubuntu22.04&#xff0c;然后点击下一步。…...

redisson使用过程常见问题汇总

文章目录 常见报错1. 配置方式使用错误2. 版本差异报错3. 配置文件中配置了密码或者配置错误4. 字符集和序列化方式配置问题5. Redisson的序列化问题6. 连接池问题&#xff1a;7. Redisson的高可用性问题&#xff1a;8. Redisson的并发问题9. Redisson的性能问题 2. 参考文档 常…...

代码随想录训练营 DP序列

代码随想录训练营 DP序列 718. 最长重复子数组&#x1f338;code 674. 最长连续递增序列&#x1f338;code 300.最长递增子序列&#x1f338;code 最后一题很巧妙&#xff0c;不能单纯的去把DP当作板子题&#xff0c;得思考才能得到最佳方式 718. 最长重复子数组&#x1f338; …...

Datastage部署与使用

Datastage部署与使用 - 码农教程 https://www.cnblogs.com/lanston/category/739553.html Streamsets定时拉取接口数据同步到HBase集群_streamsets api_webmote的博客-CSDN博客 【SDC】StreamSets实战之路-28-实战篇- 使用StreamSets实时采集指定数据目录文件并写入库Kudu_菜…...

【实用工具】Centos 安装ARL灯塔

文章目录 docker 安装安装docker-compose配置镜像加速器ARL安装和启动 docker 安装 yum install https://download.docker.com/linux/fedora/30/x86_64/stable/Packages/containerd.io-1.2.6-3.3.fc30.x86_64.rpm yum install docker-ce (若出现无法找到包可能是镜像源问题) 更…...

IP地址定位基础数据采集

在互联网时代&#xff0c;IP地址定位技术已经成为了广泛应用的一项重要技术。无论是用于网络安全、广告投放、市场调研还是用户体验优化&#xff0c;IP地址定位技术都发挥着关键作用。 什么是IP地址定位&#xff1f; IP地址定位是一种技术&#xff0c;它通过IP地址来确定设备…...

leetcode做题笔记138. 复制带随机指针的链表

给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节点的 n…...

分布式文件系统的新兴力量:揭秘Alluxio的元数据管理机制【文末送书】

文章目录 写在前面01 分布式文件系统元数据的常见类型1.1 文件&#xff08;inode&#xff09;元数据1.2 数据块&#xff08;block&#xff09;元数据1.3 Worker元数据 02 分布式文件系统元数据的存储模式2.1 元数据存储在堆上&#xff08;HEAP模式&#xff09;2.2 元数据存储在…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...