数据结构和算法之二分法查找
二分法查找,也称作二分查找或折半查找,是一种在有序数组中快速查找特定元素的算法。它采用分治法思想,通过将问题划分为规模更小的子问题,并且通过对子问题的查找来解决原问题。
二分法查找的思路是不断地将数组一分为二,然后判断目标值在哪一部分,进而在该部分继续进行二分查找。具体步骤如下:
- 首先,设置左边界
left为0,右边界right为数组的长度减1。 - 然后,计算中间值
mid为左边界与右边界的平均值,并取整。 - 接着,比较中间值
arr[mid]与目标值target的大小。如果相等,则返回索引mid。 - 如果
arr[mid]大于target,说明目标值在左半部分,将右边界right更新为mid-1。 - 如果
arr[mid]小于target,说明目标值在右半部分,将左边界left更新为mid+1。 - 重复步骤2至5,直到左边界大于右边界,表示数组中无目标值,返回-1。
说明:
- 开始时,初始化左指针l指向数组的首元素,右指针r指向数组的尾元素。
- 判断左指针l是否大于右指针r,如果是则表示没有找到目标值,结束查找。
- 每次都取左指针l和右指针r中间的元素作为中间值。
- 判断中间值是否等于目标值,如果是则表示找到目标值,结束查找。
- 如果中间值大于目标值,说明目标值在左半部分,更新右指针r为中间值的前一个位置,继续查找。
- 如果中间值小于目标值,说明目标值在右半部分,更新左指针l为中间值的后一个位置,继续查找。
- 继续进行以上步骤,直到找到目标值或者确定没有目标值。
示例代码:
function binarySearch(arr, target) {let left = 0; // 定义左边界指针为数组的起始位置let right = arr.length - 1; // 定义右边界指针为数组的末尾位置while (left <= right) { // 当左边界指针小于等于右边界指针时执行循环let mid = Math.floor((left + right) / 2); // 计算中间元素的位置,向下取整if (arr[mid] === target) { // 如果中间元素等于目标值return mid; // 返回中间元素的位置} else if (arr[mid] < target) { // 如果中间元素小于目标值left = mid + 1; // 移动左边界指针到中间元素的下一个位置} else { // 如果中间元素大于目标值right = mid - 1; // 移动右边界指针到中间元素的前一个位置}}return -1; // 如果循环结束仍未找到目标值,则返回-1
}// 示例使用
let arr = [1, 3, 5, 7, 9];
let target = 5;let result = binarySearch(arr, target);
console.log(result); // 输出 2
在上面的示例中,提供了一个有序数组 arr 和目标值 target,然后调用 binarySearch 函数进行二分查找。最后输出的结果为目标值在数组中的索引,如果不存在则返回-1。
| 左边界指针 | 右边界指针 | 中间元素位置 | 中间元素值 | 目标值 | 结果 |
|---|---|---|---|---|---|
| 0 | 4 | 2 | 5 | 5 | 2 |
相关文章:
数据结构和算法之二分法查找
二分法查找,也称作二分查找或折半查找,是一种在有序数组中快速查找特定元素的算法。它采用分治法思想,通过将问题划分为规模更小的子问题,并且通过对子问题的查找来解决原问题。 二分法查找的思路是不断地将数组一分为二…...
系统日期如何在页面展示,框架是react或者vue3
安装插件dayjs或者moment.js 2.使用setInterval(useInterval)或者requestAnimationFrame react项目中useInterval的代码示例: import React, {useState } from react; import { useInterval } from "ahooks"; import moment fro…...
(二十二)大数据实战——Flume数据采集之故障转移案例实战
前言 本节内容我们完成Flume数据采集的故障转移案例,使用三台服务器,一台服务器负责采集nc数据,通过使用failover模式的Sink处理器完成监控数据的故障转移,使用Avro的方式完成flume之间采集数据的传输。整体架构如下:…...
前端小案例3:Flex弹性布局行内元素宽度自适应
前端小案例3:Flex弹性布局行内元素宽度自适应 项目背景:需要在一行上展示空调设备的三个模式(制冷、制热、通风)或者两个模式(制冷、制热);因为不同产品的模式数量不同,因此需要让模…...
纳尼?小说还要用看的?这可以听!无广!
这是一款听书软件,可以自定义书源,自己设置书架,页面简单易操作,无广告。 支持直接搜索书名,链接,图文,本地文件等方式听书 拥有30多主播声音,分类细致 支持倍速、添加BGM等...
【微服务部署】四、Jenkins一键打包部署NodeJS(Vue)前端项目步骤详解
本文介绍使用Jenkins一键将NodeJS(Vue)前端项目打包并上传到生产环境服务器,这里使用的是直接打包静态页面,发送到远程服务器Nginx配置目录的方式,首先确保服务器环境配置好,安装Nginx,运行目录…...
【前端】禁止别人调试自己的前端页面代码
无限debugger 前端页面防止调试的方法主要是通过不断 debugger 来疯狂输出断点,因为 debugger 在控制台被打开的时候就会执行由于程序被 debugger 阻止,所以无法进行断点调试,所以网页的请求也是看不到的代码如下: /** * 基础禁止…...
UDP的可靠性传输
UDP系列文章目录 第一章 UDP的可靠性传输-理论篇(一) 第二章 UDP的可靠性传输-理论篇(二) 文章目录 UDP系列文章目录前言1.TCP 和UDP格式对比2.UDP分片原理3.UDP 传输层应该注意问题4.MTU5.UDP 分片机制设计重点 一、ARQ协议什么…...
科研笔记:TPAMI submission guideline
1 author information Author Information - IEEE Transactions on Pattern Analysis and Machine Intelligence | IEEE Computer Society Digital Library 1.1 会议期刊extension 当一个TPAMI的提交基于之前的会议论文时,IEEE要求期刊论文是之前出版物的“实质…...
Python文件操作(02):打开文件、读文件、关闭文件
一、读文本文件 打开文件读文件内容关闭文件 1、在读取文件内容后进行解码操作 """ 1. 打开文件- 路径:相对路径:当前项目(读文件.py)所在的目录下查找需要读取的文件绝对路径:文件--右键--Copy Pat…...
C语言访问Mysql
文章目录 C语言访问Mysql1. 环境设置2. mysql接口介绍(1) 初始化mysql_init()(2) 链接数据库mysql_real_connect(3) 下发mysql命令mysql_query()(4) 获取执行结果mysql_store_result(5) 释放结果集mysql_free_result()(6) 获取结果行数mysql_num_rows(7) 获取结果列数mysql_num…...
软件设计师(十)网络与信息安全基础知识
计算机网络是由多台计算机组成的系统,与传统的单机系统、多机系统相比有很大的区别。 一、网络概述 计算机网络是计算机技术与通信技术相结合的产物,它实现了远程通信、远程信息处理和资源共享。 1、计算机网络的概念 计算机网络的定义是利用通信设备…...
蓝桥杯官网填空题(换零钞)
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 X 星球的钞票的面额只有:100 元,5 元,2 元,1 元,共 4 种。 小明去 X 星旅游,他手里只有 2 张…...
JavaFX之Stage
Stage(舞台),它代表了一个顶级窗口,是JavaFX应用程序的主要容器。Stage可以包含多个场景(Scene),每个场景可以包含各种用户界面元素(如按钮、文本框等)。Stage提供了许多…...
深度翻页导出导致慢SQL,mysqlCPU飙升优化方案
慢SQL原因分析: 1.深度翻页 2.多表JOIN 3. 大IN 4. id倒排序 本文针对深度翻页的优化进行探讨 方案1: 将limit offset, pageSize的方式改成 id > xx limit pageSize. 这样能走Id索引,提高速度。 缺点:不能使用多线程…...
小谈设计模式(1)—总序
小谈设计模式(1)—总序 开始操作设计模式总论设计模式是什么组成要素模式名称问题描述解决方案效果描述 设计模式有什么作用提供可重用的解决方案提高代码的可读性和可维护性促进代码的可扩展性提高代码的灵活性和可重用性促进团队合作和沟通作用总结 为…...
【c++】stringstream基础:实现数据类型转换和字符串分割
传统实现整型转换为字符串需要使用itoa或者sprintf,对于itoa和atoi的使用可以看文章: atoi和itoa极简无废话概述 但是用这两个函数进行转换时,所需要的空间事先不确定,所以可能造成程序崩溃,今天介绍的stringstream可…...
Java基础学习笔记-5
前言 Java编程语言是一门广泛应用于软件开发领域的高级编程语言。它的强大特性和跨平台性使其成为许多开发者的首选语言。本文将介绍一些Java编程的关键概念,包括函数重载、可变参数、值传递、递归等,这些概念是Java编程的基础,对于理解和掌…...
合同交付类项目如何高效管理?
美国项目管理协会(PMI)保罗格蕾斯曾说:“当今社会,一切都是项目,一切也将成为项目。”在“万事皆项目”的背景下,企业在运营过程中会产生大量的项目型业务活动,例如:举办市场活动、产品研发、进行企业内训、采购招标、工程建设等等。那么按照…...
两性养生网站源码 生活类减肥网站源码 健康网模板源码 支持QQ登录和百度主动推送
本套模板非常适合生活类,两性类,减肥类等等类型的网站,这类型网站比较好做流量,因为客户群体众多, 可以自行改内容为其他类型网站模板总体非常简洁漂亮,配色合理,视觉舒服,并且配合…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
EEG-fNIRS联合成像在跨频率耦合研究中的创新应用
摘要 神经影像技术对医学科学产生了深远的影响,推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下,基于神经血管耦合现象的多模态神经影像方法,通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里,本研…...
Qt Quick Controls模块功能及架构
Qt Quick Controls是Qt Quick的一个附加模块,提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中,这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构,与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...
C# WPF 左右布局实现学习笔记(1)
开发流程视频: https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码: GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用(.NET Framework) 2.…...
