数据结构——二分查找法
二分查找法(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;
}
相关文章:
数据结构——二分查找法
二分查找法(Binary Search)是一种高效的查找算法,通常用于在已排序的数组或列表中查找特定的目标值。这个算法的基本思想是不断将查找范围缩小为原来的一半,直到找到目标值或确定目标值不存在。 二分查找是一种在每次比较之后将查…...
服务端渲染(SSR):提升Web应用性能和用户体验的关键技术
💂 个人网站:【工具大全】【游戏大全】【神级源码资源网】🤟 前端学习课程:👉【28个案例趣学前端】【400个JS面试题】💅 寻找学习交流、摸鱼划水的小伙伴,请点击【摸鱼学习交流群】 引言 服务端渲染&#…...
如何工作和生活相平衡?
之前待过一家外企,他们的口号是 Balancing work and life,工作和生活相平衡。辗转几家公司之后,发现这个越来越难了,越来越少的时间投入家庭和自己的生活。 人生的意义 (AI) 人生的意义是一个深奥而复杂的…...
semaphere部署,配置ldap
在处理 Ansible 相关项目时,我们经常面临繁琐的命令行操作,这对于不熟悉命令行的用户来说可能是一个挑战。此外,当项目规模扩大时,跟踪和管理多个 playbook 变得困难,同时缺乏对失败的及时通知和访问控制。这些问题催生…...
Java 泛型 T,E,K,V,?
泛型带来的好处 在没有泛型的情况的下,通过对类型 Object 的引用来实现参数的“任意化”,“任意化”带来的缺点是要做显式的强制类型转换,而这种转换是要求开发者对实际参数类型可以预知的情况下进行的。对于强制类型转换错误的情况…...
软件测试技术之地图导航的测试用例
外观测试 屏幕显示不能有花屏、黑点和闪屏,清晰度、亮度、颜色要正常。 检测所有按键都能起到相应作用,是否手感不良。 UI显示状态、颜色、清晰度、效果。 控制:放大,缩小,音量调节功能测试。 交叉路口查询测试&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:flex的子组件设置了flex:1;就能让他填满整个容器,如果有多个就平均 flex:1;是另外三个样式属性的简写,等同 flex-grow: 0; flex-shrink: 1; flex-basis: auto;我们就针…...
discuzQ安装
我们开始配置php,安装两个扩展。 在宝塔面板中,单击软件商城->已安装,查找已安装的 PHP 软件。 然后在 php 管理中,单击禁用函数,进入设置页面。 在列表中单击删除函数 putenv、readlink、symlink、shell_exec ,…...
深入解析NLP情感分析技术:从篇章到属性
目录 1. 情感分析概述1.1 什么是情感分析?- 情感分析的定义- 情感分析的应用领域 1.2 为什么情感分析如此重要?- 企业和研究的应用- 社交媒体和公共意见的影响 2. 篇章级情感分析2.1 技术概览- 文本分类的基本概念- 机器学习与深度学习方法- 词嵌入的力量…...
JVM的双亲委派模型
定义与本质: 类加载器用来把类文件加载到JVM内存中。从JDK1.2开始,类加载过程采用双亲委派模型,保证Java平台安全。 父类委托的定义: 一个类加载器在接到加载类请求的时候,首先不会去加载这个类,而是把这个…...
js中如何判断一个变量是否为数字类型?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐使用Number.isNaN()方法⭐使用正则表达式⭐使用isNaN()函数⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个…...
使用阿里PAI DSW部署Stable Diffusion WebUI
进入到网址https://pai.console.aliyun.com/里边。 点击创建实例。 把实例名称填写好,选择GPU规格,然后选择实例名称是ecs.gn6v-c8g1.2xlarge。 选择stable-diffusion-webui-env:pytorch1.13-gpu-py310-cu117-ubuntu22.04,然后点击下一步。…...
redisson使用过程常见问题汇总
文章目录 常见报错1. 配置方式使用错误2. 版本差异报错3. 配置文件中配置了密码或者配置错误4. 字符集和序列化方式配置问题5. Redisson的序列化问题6. 连接池问题:7. Redisson的高可用性问题:8. Redisson的并发问题9. Redisson的性能问题 2. 参考文档 常…...
代码随想录训练营 DP序列
代码随想录训练营 DP序列 718. 最长重复子数组🌸code 674. 最长连续递增序列🌸code 300.最长递增子序列🌸code 最后一题很巧妙,不能单纯的去把DP当作板子题,得思考才能得到最佳方式 718. 最长重复子数组🌸 …...
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地址定位基础数据采集
在互联网时代,IP地址定位技术已经成为了广泛应用的一项重要技术。无论是用于网络安全、广告投放、市场调研还是用户体验优化,IP地址定位技术都发挥着关键作用。 什么是IP地址定位? IP地址定位是一种技术,它通过IP地址来确定设备…...
leetcode做题笔记138. 复制带随机指针的链表
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 n…...
分布式文件系统的新兴力量:揭秘Alluxio的元数据管理机制【文末送书】
文章目录 写在前面01 分布式文件系统元数据的常见类型1.1 文件(inode)元数据1.2 数据块(block)元数据1.3 Worker元数据 02 分布式文件系统元数据的存储模式2.1 元数据存储在堆上(HEAP模式)2.2 元数据存储在…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
