当前位置: 首页 > 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 的丰富功能来构建应用程序。…...

开源工具TranslucentTB启动错误0x800401E3完整解决方案

开源工具TranslucentTB启动错误0x800401E3完整解决方案 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB TranslucentTB是一款广受欢迎的Wi…...

美的集团2025年营收创新高、利润100%分红 落地1.3万个AI智能体

3月30日&#xff0c;美的集团发布2025年年报&#xff0c;实现营业总收入4585亿元&#xff0c;同比增长12.1%&#xff1b;归属于上市公司股东的净利润439.5亿元&#xff0c;同比上升14%。在业绩再创新高的同时&#xff0c;伴随我国“人工智能”行动的全面实施&#xff0c;美的集…...

DeepSeek句式重构指令怎么用?手把手教你降AI率超过30%

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

基于MCGS嵌入版7.7的全自动洗车机组态仿真程序编写与流程图详解

MCGS洗车程序 MCGS嵌入版7.7组态仿真程序 全自动洗车机&#xff0c;脚本程序编写 有完整的流程图"这洗车机PLC程序怎么又卡在喷淋环节了&#xff1f;"凌晨两点的工控车间里&#xff0c;我盯着MCGS嵌入版的仿真界面直挠头。全自动洗车机的脚本调试真是个磨人的小妖精&…...

OpCore-Simplify:如何将黑苹果EFI配置从3小时缩短到15分钟?

OpCore-Simplify&#xff1a;如何将黑苹果EFI配置从3小时缩短到15分钟&#xff1f; 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 在开源系统定制领域…...

零基础教程:5个简单步骤用Mi-Create打造个性化小米手表表盘

零基础教程&#xff1a;5个简单步骤用Mi-Create打造个性化小米手表表盘 【免费下载链接】Mi-Create Unofficial watchface creator for Xiaomi wearables ~2021 and above 项目地址: https://gitcode.com/gh_mirrors/mi/Mi-Create Mi-Create是一款专为小米穿戴设备用户打…...

CosyVoice2-0.5B效果实测:背景噪音音频对克隆效果影响量化

CosyVoice2-0.5B效果实测&#xff1a;背景噪音音频对克隆效果影响量化 1. 测试背景与目的 声音克隆技术近年来发展迅猛&#xff0c;阿里开源的CosyVoice2-0.5B作为一款强大的零样本语音合成系统&#xff0c;能够在短短3秒内复刻任意说话人的声音。但在实际应用中&#xff0c;…...

IntelliJ IDEA中SVN与Git版本管理的高效配置指南

1. 为什么需要版本管理工具&#xff1f; 如果你曾经因为误删代码而熬夜重写&#xff0c;或者因为团队协作时文件覆盖而崩溃&#xff0c;那你一定需要版本管理工具。想象一下&#xff0c;代码就像写作文时的草稿纸——每次修改都保留历史版本&#xff0c;随时可以回退到上周二下…...

Redis 相关命令详解及其原理

Redis 相关命令详解及其原理 文章目录Redis 相关命令详解及其原理1. Redis 简介2. Redis 安装2.1 包管理器安装2.2 源码编译安装2.4 验证安装3. Redis 基础原理3.1 单线程模型3.2 底层数据结构概述4. 数据类型详解4.1 String&#xff08;字符串&#xff09;底层存储结构常用命令…...

VSCode配置PyTorch开发环境:从CUDA版本检查到镜像源加速(附常见报错解决方案)

VSCode配置PyTorch开发环境&#xff1a;从CUDA版本检查到镜像源加速&#xff08;附常见报错解决方案&#xff09; 在深度学习领域&#xff0c;PyTorch凭借其动态计算图和易用性已成为研究者和开发者的首选框架。然而&#xff0c;配置PyTorch开发环境时&#xff0c;CUDA版本匹配…...