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

数据结构之折半查找

折半查找(Binary Search),也称为二分查找,是一种在有序数组中查找特定元素的搜索算法。其工作原理是,通过不断将待查找的区间分成两半,并判断待查找的元素可能存在于哪一半,然后继续在存在可能性的那一半区间中查找,直到找到该元素或者区间被缩小为0为止。

折半查找的基本步骤

1、初始化:

确定查找范围的上下界,即查找区间的起始位置low和结束位置high,通常初始时low = 0,high = 数组长度 - 1。

2、循环查找:

当low <= high时,执行以下步骤:

计算中间位置mid = (low + high) // 2(注意使用整除以避免浮点数)。
判断中间位置的元素是否是要查找的元素,即arr[mid] == target:
如果是,则查找成功,返回中间位置mid(或该位置的索引mid,取决于具体实现)。
如果不是,则判断target与arr[mid]的大小关系,并据此调整查找范围:
如果target < arr[mid],则说明target在左半部分,更新high = mid - 1。
如果target > arr[mid],则说明target在右半部分,更新low = mid + 1。

3、查找失败:

如果循环结束时仍未找到target,则说明数组中不存在该元素,返回查找失败的信息(通常是-1或特定值)。

折半查找的Python示例

def binary_search(arr, target):"""折半查找(二分查找):param arr: 有序数组:param target: 要查找的目标值:return: 目标值在数组中的索引,如果未找到则返回-1"""low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return mid  # 找到目标值,返回索引elif arr[mid] < target:low = mid + 1  # 调整查找范围到右半部分else:high = mid - 1  # 调整查找范围到左半部分return -1  # 未找到目标值,返回-1# 示例
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7result = binary_search(arr, target)
print(f"元素{target}在数组中的索引为:{result}")  # 输出:元素7在数组中的索引为:3

折半查找的优缺点

优点:
查找速度快,时间复杂度为O(log n),其中n是数组的长度。
对于大数据集,查找效率远高于顺序查找。

缺点:
要求待查找的数组必须是有序的。
数组必须有随机访问的能力,即可以使用索引直接访问元素,这限制了它在链表等数据结构上的应用。
当数据集非常大时,需要较大的内存空间来存储整个数组。

相关文章:

数据结构之折半查找

折半查找&#xff08;Binary Search&#xff09;&#xff0c;也称为二分查找&#xff0c;是一种在有序数组中查找特定元素的搜索算法。其工作原理是&#xff0c;通过不断将待查找的区间分成两半&#xff0c;并判断待查找的元素可能存在于哪一半&#xff0c;然后继续在存在可能性…...

linux高级学习12

24.9.9学习目录 一.条件变量 一.条件变量 通常条件变量和互斥锁同时使用&#xff1b; 条件变量是用来阻塞线程&#xff0c;其本身并不是锁&#xff0c;直到达到特定的要求&#xff1b; &#xff08;1&#xff09;条件变量初始化 #include <pthread.h> int pthread_con…...

leetcode:3174 清除数字 使用栈,时间复杂度O(n)

3174 清除数字 题目链接 题目描述 给你一个字符串 s 。 你的任务是重复以下操作删除 所有 数字字符&#xff1a; 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。 请你返回删除所有数字字符以后剩下的字符串。 示例 1&#xff1a; 输入&#xff1a;s "abc…...

神经网络卷积操作

文章目录 一、nn.Conv2d二、卷积操作原理三、代码实现卷积操作 一、nn.Conv2d nn.Conv2d 是 PyTorch 中的一个类&#xff0c;它代表了一个二维卷积层&#xff0c;通常用于处理图像数据。在深度学习和计算机视觉中&#xff0c;卷积层是构建卷积神经网络&#xff08;CNN&#xf…...

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口&#xff0c;引入&#xff1a; 滑动窗口&#xff0c;本质&#xff1a;就是同向双指针&#xff1b; 1.⻓度最⼩的⼦数组&#xff08;medium&#xff09; 1.解析&#xff1a;给我们一个数组nums&#xff0c;要我们找出最小子数组的和target&#xff0c;首先想到的…...

【机器学习-三-无监督学习】

无监督学习 什么是无监督学习分类聚类降维 有监督和无监督学习的区别 上一节介绍了监督学习&#xff0c;下面来介绍无监督学习&#xff0c;这也是最广泛应用的算法。 什么是无监督学习 上一节中&#xff0c;我们知道了监督学习是通过 对算法&#xff0c;**输入一对数据&#x…...

JAVA基础:Lambda表达式(上)

前言 Lambda表达式是jdk1.8的一个新特性&#xff0c;他属于一种语法堂主要作用是对匿名内部类语法简化 lambda基本应用 lambda表达式想要优化匿名内部类是有前提条件&#xff0c;首先必须是一个接口&#xff0c;而且要求接口中只能有1个抽象方法&#xff0c;称之为函数式接口…...

Vue使用fetch获取本地数据

&#xff08;1&#xff09;使用get test.json文件 { "list":[111,222,333] } <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initi…...

《酒饮真经》秘籍4,让你的酒场技巧更上一层楼!

在酒桌这一独特的舞台上&#xff0c;每个人都扮演着不同的角色&#xff0c;或攻或守&#xff0c;尽显智慧与风度。对于不擅长喝酒的人来说&#xff0c;如何在推杯换盏间既保护自己又不失礼节&#xff0c;是值得我们仔细研究的。下面是酱酒亮哥为您整理的一系列实用的酒桌攻防秘…...

回车符与快捷键记录

一.在Windows和Linux操作系统中&#xff0c;回车符&#xff08;或称为换行符&#xff09;的处理方式区别 1.Windows下的回车符 在Windows系统中&#xff0c;回车符通常是由两个字符组成的序列&#xff1a;回车符&#xff08;Carriage Return&#xff0c;简称CR&#xff0c;AS…...

计算机网络-VRRP工作原理

一、VRRP工作原理 前面我们大概了解了VRRP的一些基础概念&#xff0c;现在开始学习VRRP的技术原理。VRRP的选举及工作步骤&#xff1a; 确定网关地址 选举主备 主设备发送VRRP报文通知Backup设备 主设备响应终端ARP并维持在Master状态 终端正常发送报文到网关进行转发 因为我们…...

6.5椒盐噪声

在OpenCV中联合C给一张图片加上椒盐噪声&#xff08;Salt and Pepper Noise&#xff09;可以通过随机选择像素点并将其置为黑色&#xff08;0&#xff09;或白色&#xff08;255&#xff09;来实现。椒盐噪声是一种随机噪声&#xff0c;通常表现为图像中的孤立黑点&#xff08;…...

CSS样式的引用方式以及选择器使用

1. CSS 引用方式 CSS 可以通过三种方式引用到 HTML 文件中&#xff1a; 行内样式&#xff08;Inline Styles&#xff09;&#xff1a;直接在 HTML 元素中定义样式。内部样式表&#xff08;Internal CSS&#xff09;&#xff1a;在 HTML 文档的 <head> 部分使用 <sty…...

Python Flask_APScheduler定时任务的正确(最佳)使用

描述 APScheduler基于Quartz的一个Python定时任务框架&#xff0c;实现了Quartz的所有功能。最近使用Flask框架使用Flask_APScheduler来做定时任务&#xff0c;在使用过程当中也遇到很多问题&#xff0c;例如在定时任务调用的方法中需要用到flask的app.app_context()时&#…...

Linux命名管道

​ ​通信的前提是让不同的进程看到同一份资源&#xff0c;因为路径是具有唯一性的&#xff0c;所以我们可以使用路径文件名来唯一的让不同进程看到同一份资源&#xff0c;实现没有血缘关系的两个进程进行管道通信 1.指令级 mkfifio&#xff08;FILENAME,0666&#xff09; …...

Xinstall助力App全渠道统计,参数传递下载提升用户体验!

在移动互联网时代&#xff0c;App已成为我们日常生活中不可或缺的一部分。然而&#xff0c;对于App开发者来说&#xff0c;如何有效地推广和运营自己的应用&#xff0c;却是一个不小的挑战。尤其是在面对众多渠道、复杂的数据统计和用户需求多样化的情况下&#xff0c;如何精准…...

【时时三省】(C语言基础)指针进阶 例题4

山不在高&#xff0c;有仙则名。水不在深&#xff0c;有龙则灵。 ----CSDN 时时三省 strlen是求字符串长度 这个需要算上&#xff3c;0 第一个arr 是打印6 因为它加上&#xff3c;0是有六个元素 第二个arr0 数组名相当于首元素的地址 a的地址加0还是a的地址 所以这个地方还是…...

k8s的配置管理

一、配置管理分为两种&#xff1a; 1. 加密配置&#xff1a;用来保存密码和token密钥对以及其它敏感的k8s资源。 2.应用配置&#xff1a;我们需要定制化的给应用进行配置&#xff0c;我们需要把定制好的配置文件同步到pod当中的容器。 二、加密配置 1.secret三种类型&#xf…...

JAVA- 多线程

一&#xff0c;多线程的概念 1.并行与并发 并行&#xff1a;多个任务在同一时刻在cpu 上同时执行并发&#xff1a;多个任务在同一时刻在cpu 上交替执行 2.进程与线程 进程&#xff1a;就是操作系统中正在运行的一个应用程序。所以进程也就是“正在进行的程序”。&#xff0…...

【Qt】解决设置QPlainTextEdit控件的Tab为4个空格

前言 PyQt5 是一个用于创建跨平台桌面应用程序的 Python 绑定集合&#xff0c;它提供了对 Qt 应用程序框架的访问。用于开发具有图形用户界面&#xff08;GUI&#xff09;的应用程序&#xff0c;以及非GUI程序。PyQt5 使得 Python 开发者可以使用 Qt 的丰富功能来构建应用程序。…...

第一次降AIGC率不知道从哪入手?这份保姆级操作手册帮你

第一次操作的话&#xff0c;照着下面的步骤来&#xff0c;15分钟内搞定降AIGC率、降AI工具保姆级测评2026、降AI。 工具选嘎嘎降AI&#xff08;www.aigcleaner.com&#xff09;&#xff0c;达标率99.26%&#xff0c;有退款保障&#xff0c;操作也不复杂。 准备工作 需要准备的…...

OpenHarmony基线移植实战:从开源仓到定制仓的完整路径

1. 为什么需要移植OpenHarmony基线&#xff1f; 第一次接触OpenHarmony基线移植时&#xff0c;我也很困惑&#xff1a;为什么不能直接用官方开源代码&#xff1f;非要折腾这一套移植流程&#xff1f;直到在实际项目中踩了几个坑才明白&#xff0c;基线移植是产品开发的必经之路…...

SpringBoot集成TTL实现Feign与线程池的TraceId无缝传递(实战优化版)

1. 问题背景与核心挑战 在分布式系统中&#xff0c;日志链路追踪是排查问题的关键手段。想象一下这样的场景&#xff1a;用户请求从网关进入&#xff0c;经过多个微服务处理&#xff0c;每个服务又可能调用其他服务或使用线程池异步处理。当出现问题时&#xff0c;如何快速定位…...

从LFA到TI-LFA:一张图看懂华为IGP FRR技术演进与选型指南

从LFA到TI-LFA&#xff1a;华为IGP FRR技术全景解析与实战选型 当视频会议因网络抖动出现卡顿时&#xff0c;当金融交易因路由收敛延迟导致订单丢失时&#xff0c;网络工程师们开始意识到&#xff1a;传统的IGP收敛机制已无法满足现代业务对可靠性的苛刻要求。这背后是毫秒级故…...

离线语音智能处理平台Buzz:本地化音频转文本全攻略

离线语音智能处理平台Buzz&#xff1a;本地化音频转文本全攻略 【免费下载链接】buzz Buzz transcribes and translates audio offline on your personal computer. Powered by OpenAIs Whisper. 项目地址: https://gitcode.com/GitHub_Trending/buz/buzz 在当今信息驱动…...

Peroxidase-conjugated AffiniPure Goat Anti-Human IgG:高酶活,低背景,精准定量人源抗体

在现代生命科学研究中&#xff0c;抗体是实现特定分子识别和信号检测的核心工具。其中&#xff0c;二抗作为连接一抗与检测系统的重要桥梁&#xff0c;其特异性和灵敏度直接影响实验结果的准确性与可靠性。Peroxidase-conjugated AffiniPure Goat Anti-Human IgG, Fcγ Fragmen…...

StructBERT-WebUI部署案例:AI客服中台语义路由模块集成实践

StructBERT-WebUI部署案例&#xff1a;AI客服中台语义路由模块集成实践 1. 项目背景与价值 在现代AI客服系统中&#xff0c;语义理解是核心能力之一。当用户提出"我的订单怎么还没到"时&#xff0c;系统需要准确理解这其实是在询问"物流状态"&#xff0c…...

告别手动调参!用大津法(OTSU)实现8路灰度传感器的自适应巡线(附完整C代码)

告别手动调参&#xff01;用大津法实现8路灰度传感器的智能巡线方案 当你在电赛现场调试机器人巡线时&#xff0c;是否经历过这样的场景&#xff1a;刚在A场地调好的阈值参数&#xff0c;换到B场地就完全失灵&#xff1b;上午还能精准巡线的小车&#xff0c;下午因为光照变化就…...

LongCat-Video:AI视频生成技术的范式突破与实践指南

LongCat-Video&#xff1a;AI视频生成技术的范式突破与实践指南 【免费下载链接】LongCat-Video 项目地址: https://ai.gitcode.com/hf_mirrors/meituan-longcat/LongCat-Video 在数字内容创作领域&#xff0c;AI视频生成技术正经历从实验性探索到产业化应用的关键转折…...

如何高效突破内容付费墙:Bypass Paywalls Clean浏览器扩展深度技术解析

如何高效突破内容付费墙&#xff1a;Bypass Paywalls Clean浏览器扩展深度技术解析 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在数字内容访问受限的时代&#xff0c;Bypass Payw…...