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

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...