当前位置: 首页 > 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 元数据存储在…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...