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

Hello 算法10:搜索

https://www.hello-algo.com/chapter_searching/binary_search/

二分查找法

给定一个长度为 n的数组 nums ,元素按从小到大的顺序排列,数组不包含重复元素。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素,则返回 -1 。

# 首先初始化 i=0,j=n-1, 代表搜索区间是[0,n-1]
# 然后,循环执行以下2个步骤
# 1:m = (i+j)/2 ,向下取整,求出搜索区间的中间点
# 2:判断nums[m]和target的大小关系,有以下三种情况:
#    a:nums[m] > target,说明目标在区间[i,m-1],所以让j = m - 1
#    b: nums[m] < target,说明目标在区间[m+1,j],所以让i = m + 1
#    c:说明已经找到目标值,因此返回索引m

代码如下:

def binary_search(nums: list[int], target: int):i, j = 0, len(nums) - 1while i <= j:m = (i+j) // 2if nums[m] > target:j = m -1elif nums[m] < target:i = m + 1else:return mreturn -1

优点:效率高,无需额外空间

缺点:仅适用于有序数据,仅使用数数组搜索,当数据量较小时,线性查找速度更快。

二分查找插入点

给定一个长度为 n的有序数组 nums 和一个元素 target ,数组不存在重复元素。现将 target 插入到数组 nums 中,并保持其有序性。若数组中已存在元素 target ,则插入到其左方。请返回插入后 target 在数组中的索引。

  1. 当target存在时,插入的索引就是taget的位置
  2. 当target不存在时:如果target > nums[m],让i = m +1 ,所以i在靠着大于等于目标的位置移动;反之j在靠着小于等于目标的位置移动,这导致的结果就是,最终i等于第一个比目标大的元素,j指向首个比目标小的元素。

可知,最终返回i即是插入的位置

def binary_search_insertion_simple(nums: list[int], target: int) -> int:"""二分查找插入点(无重复元素)"""i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]while i <= j:m = (i + j) // 2  # 计算中点索引 mif nums[m] < target:i = m + 1  # target 在区间 [m+1, j] 中elif nums[m] > target:j = m - 1  # target 在区间 [i, m-1] 中else:return m  # 找到 target ,返回插入点 m# 未找到 target ,返回插入点 ireturn i

重复值的情况

在上一题的基础上,规定数组可能包含重复元素,其余不变

def binary_search_insertion(nums: list[int], target: int) -> int:"""二分查找插入点(存在重复元素)"""i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]while i <= j:m = (i + j) // 2  # 计算中点索引 mif nums[m] < target:i = m + 1  # target 在区间 [m+1, j] 中elif nums[m] > target:j = m - 1  # target 在区间 [i, m-1] 中else:j = m - 1  # 首个小于 target 的元素在区间 [i, m-1] 中# 返回插入点 ireturn i

查找左边界

def binary_search_left_edge(nums: list[int], target: int) -> int:"""二分查找最左一个 target"""# 等价于查找 target 的插入点i = binary_search_insertion(nums, target)# 未找到 target ,返回 -1if i == len(nums) or nums[i] != target:return -1# 找到 target ,返回索引 ireturn i

查找右边界

替换在 nums[m] == target 情况下的指针收缩操作即可,接下来介绍一些取巧的办法

  1. 复用左边界法,使查找目标加一

    def binary_search_right_edge(nums: list[int], target: int) -> int:"""二分查找最右一个 target"""# 转化为查找最左一个 target + 1i = binary_search_insertion(nums, target + 1)# j 指向最右一个 target ,i 指向首个大于 target 的元素j = i - 1# 未找到 target ,返回 -1if j == -1 or nums[j] != target:return -1# 找到 target ,返回索引 jreturn j
    
  2. 转换为查找不存在的元素

    当数组不包含目标元素时,最终i和j会分别指向首个大于、小于target的元素:

    查找最左侧元素时,可以将目标设置为targe-0.5,最终返回i

    查找最右侧元素时,可以将目标设置为target+0.5,最终返回j

    在这里插入图片描述

哈希优化

在算法题中,通常通过将线性遍历替换为哈希搜索来提升时间复杂度。例如以下题目

给定一个整数数组 nums 和一个目标元素 target ,请在数组中搜索“和”为 target 的两个元素,并返回它们的数组索引。返回任意一个解即可。

线性遍历

开启一个两层循环,每次判断是否和为目标值。简单粗暴

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:"""方法一:暴力枚举"""# 两层循环,时间复杂度为 O(n^2)n = len(nums)for i in range(n):for j in range(i+1, n):if nums[i] + nums[i] == target:return [i, j]return []

哈希查找

def two_sum_hash_table(nums: list[int], target: int) -> list[int]:"""方法二:辅助哈希表"""# 辅助哈希表,空间复杂度为 O(n)dic = {}n = len(nums)for i in range(n):if target - nums[i] not in dic:dic[nums[i]] = ielse:return [dic[target - nums[i]], i]return []

搜索算法总结

搜索算法根据实现方式可以分为以下两类:

  • 通过遍历数据结构来定位元素,例如数组、图、树的遍历等
  • 利用数据结构的特性,实现高效搜索,例如二分查找、哈希查找

暴力搜索

  • 线性搜索,适用于数组、链表
  • 广度优先和深度优先搜索,适用于图、树

优点是通用性好,容易理解,不需要对数据结构做预期处理;不需要额外空间。

缺点是此类算法的时间复杂度为O(n),因此在元素较多时效率较低

自适应搜索

自适应搜索利用数据结构的特性来优化搜索

  • 二分查找,利用有序性来进行搜索,仅适用于数组
  • 哈希查找,利用哈希表将搜索数据和目标数据建立键值对映射,从而实现查询操作
  • 树查找

效率高,可达到o(logn)甚至o(1)

缺点:需要对数据进行预处理,需要额外空间

搜索方法选取

在这里插入图片描述

表 10-1 查找算法效率对比

线性搜索二分查找树查找哈希查找
查找元素O(n)O(log⁡n)O(log⁡n)O(1)
插入元素O(1)O(n)O(log⁡n)O(1)
删除元素O(n)O(n)O(log⁡n)O(1)
额外空间O(1)O(1)O(log⁡n)O(n)
数据预处理/排序 O(nlog⁡n)建树 O(nlog⁡n)建哈希表 O(n)
数据是否有序无序有序有序无序

搜索算法的选择还取决于数据体量、搜索性能要求、数据查询与更新频率等。

相关文章:

Hello 算法10:搜索

https://www.hello-algo.com/chapter_searching/binary_search/ 二分查找法 给定一个长度为 n的数组 nums &#xff0c;元素按从小到大的顺序排列&#xff0c;数组不包含重复元素。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素&#xff0c;则返回 -1 。 # 首…...

常见分类算法详解

在机器学习和数据科学的广阔领域中&#xff0c;分类算法是至关重要的一环。它广泛应用于各种场景&#xff0c;如垃圾邮件检测、图像识别、情感分析等。本文将深入剖析几种常见的分类算法&#xff0c;帮助读者理解其原理、优缺点以及应用场景。 一、K近邻算法&#xff08;K-Nea…...

推送恶意软件的恶意 PowerShell 脚本看起来是人工智能编写的

威胁行为者正在使用 PowerShell 脚本&#xff0c;该脚本可能是在 OpenAI 的 ChatGPT、Google 的 Gemini 或 Microsoft 的 CoPilot 等人工智能系统的帮助下创建的。 攻击者在 3 月份的一次电子邮件活动中使用了该脚本&#xff0c;该活动针对德国的数十个组织来传播 Rhadamanthy…...

微服务之Consul 注册中心介绍以及搭建

一、微服务概述 1.1单体架构 单体架构&#xff08;monolithic structure&#xff09;&#xff1a;顾名思义&#xff0c;整个项目中所有功能模块都在一个工程中开发&#xff1b;项目部署时需要对所有模块一起编译、打包&#xff1b;项目的架构设计、开发模式都非常简单。 当项…...

MES生产管理系统:私有云、公有云与本地化部署的比较分析

随着信息技术的迅猛发展&#xff0c;云计算作为一种新兴的技术服务模式&#xff0c;已经深入渗透到企业的日常运营中。在众多部署方式中&#xff0c;私有云、公有云和本地化部署是三种最为常见的选择。它们各自具有独特的特点和适用场景&#xff0c;并在不同程度上影响着企业的…...

【core analyzer】core analyzer的介绍和安装详情

目录 &#x1f31e;1. core和core analyzer的基本概念 &#x1f33c;1.1 coredump文件 &#x1f33c;1.2 core analyzer &#x1f31e;2. core analyzer的安装详细过程 &#x1f33c;2.1 方式一 简单但不推荐 &#x1f33c;2.2 方式二 推荐 &#x1f33b;2.2.1 安装遇到…...

个人练习之-jenkins

虚拟机环境搭建(买不起服务器 like me) 重点: 0 虚拟机防火墙关闭 systemctl stop firewalld.service systemctl disable firewalld.service 1 (centos7.6)网络配置 (vmware 编辑 -> 虚拟网络编辑器 -> 选择NAT模式 ->NAT设置查看网关) vim /etc/sysconfig/network-sc…...

初探vercel托管项目

文章目录 第一步、注册与登录第二步、本地部署 在个人网站部署的助手vercel&#xff0c;支持 Github部署&#xff0c;只需简单操作&#xff0c;即可发布&#xff0c;方便快捷&#xff01; 第一步、注册与登录 进入vercel【官网】&#xff0c;在右上角 login on&#xff0c;可登…...

软考 - 系统架构设计师 - 质量属性例题 (2)

问题1&#xff1a; 、 问题 2&#xff1a; 系统架构风险&#xff1a;指架构设计中 &#xff0c;潜在的&#xff0c;存在问题的架构决策所带来的隐患。 敏感点&#xff1a;指为了实现某个质量属性&#xff0c;一个或多个构件所具有的特性 权衡点&#xff1a;指影响多个质量属性…...

基于Python豆瓣电影数据可视化分析系统的设计与实现

大数据可视化项目——基于Python豆瓣电影数据可视化分析系统的设计与实现 2024最新项目 项目介绍 本项目旨在通过对豆瓣电影数据进行综合分析与可视化展示&#xff0c;构建一个基于Python的大数据可视化系统。通过数据爬取收集、清洗、分析豆瓣电影数据&#xff0c;我们提供了…...

【已开源】​基于stm32f103的爬墙小车

​基于stm32f103的遥控器无线控制爬墙小车&#xff0c;实现功能为可平衡在竖直墙面上&#xff0c;并进行移动和转向&#xff0c;具有超声波防撞功能。 直接上&#xff1a; 演示视频如&#xff1a;哔哩哔哩】 https://b23.tv/BzVTymO 项目说明&#xff1a; 在这个项目中&…...

PCL 基于马氏距离KMeans点云聚类

文章目录 一、简介二、算法步骤三、代码实现四、实现效果参考资料一、简介 在诸多的聚类方法中,K-Means聚类方法是属于“基于原型的聚类”(也称为原型聚类)的方法,此类方法均是假设聚类结构能通过一组原型刻画,在现实聚类中极为常用。通常情况下,该类算法会先对原型进行初始…...

libVLC 视频窗口上叠加透明窗口

很多时候&#xff0c;我们需要在界面上画一些三角形、文字等之类的东西&#xff0c;我们之需要重写paintEvent方法&#xff0c;比如像这样 void Widget::paintEvent(QPaintEvent *event) 以下就是重写的代码。 void Widget::paintEvent(QPaintEvent *event) {//创建QPainte…...

MySQL基础入门上篇

MySQL基础 介绍 mysql -uroot -p -h127.0.0.1 -P3306项目设计 具备数据库一定的设计能力和操作数据的能力。 数据库设计DDL 定义 操作 显示所有数据库 show databases;创建数据库 create database db02;数据库名唯一&#xff0c;不能重复。 查询是否创建成功 加入一些…...

Docker搭建FFmpeg

FFmpeg 是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的完整解决方案。FFmpeg 包含了领先的音视频编解码库libavcodec&#xff0c;可以用于各种视频格式的转换。 应用场景包括&#xff1a; 视频转换&#xff1a;把视频从一种格式转换成另一种格式。视…...

Hudi-ubuntu环境搭建

hudi-ubuntu环境搭建 运行 1.编译Hudi #1.把maven安装包上传到服务器 # 官网下载安装包 https://archive.apache.org/dist/maven/maven-3/ scp -r D:\Users\zh\Desktop\Hudi\compressedPackage\apache-maven-3.6.3-bin.tar.gz zhangheng10.8.4.212:/home/zhangheng/hudi/com…...

Hive进阶Day05

一、HDFS分布式文件存储系统 1-1 HDFS的存储机制 按块&#xff08;block&#xff09;存储 hdfs在对文件数据进行存储时&#xff0c;默认是按照128M(包含)大小进行文件数据拆分&#xff0c;将不同拆分的块数据存储在不同datanode服务器上 拆分后的块数据会被分别存储在不同的服…...

ssh爆破服务器的ip-疑似肉鸡

最近发现自己的ssh一直有一些人企图使用ssh暴力破解的方式进行密码破解.就查看了一下,真是网络安全太可怕了. 大家自己的服务器密码还是要设置好,管好,做好最基本的安全措施,不然最后只能沦为肉鸡. ssh登陆日志可以在/var/log下看到,ubuntu的话为auth.log,centos为secure文件 查…...

4.JVM八股

JVM空间划分 线程共享和线程私有 1.7&#xff1a; 线程共享&#xff1a; 堆、方法区 线程私有&#xff1a; 虚拟机栈、本地方法栈、程序计数器 本地内存 1.8&#xff1a; 线程共享&#xff1a; 堆 线程私有&#xff1a; 老三样 本地内存&#xff0c;元空间 程序计数器 …...

内网渗透系列-mimikatz的使用以及后门植入

内网渗透系列-mimikatz的使用以及后门植入 文章目录 内网渗透系列-mimikatz的使用以及后门植入前言mimikatz的使用后门植入 msf永久后门植入 &#xff08;1&#xff09;Meterpreter后门&#xff1a;Metsvc&#xff08;2&#xff09;Meterpreter后门&#xff1a;Persistence NC后…...

5G网络开通与调测ipv4

要求如下&#xff1a; 1. 勘站规划 1. 【重】首先观察NR频点&#xff0c;完成设备选型 2645--选择N41 3455--选择N78 4725--选择N79 设备选型如下&#xff1a;观察AAU的通道数&#xff0c;最大发射功率&#xff1b;选择N41的选型频段也要选41 2. …...

Spark开窗函数之ROW

Spark 1.5.x版本以后,在Spark SQL和DataFrame中引入了开窗函数,其中比较常用的开窗函数就是row_number 该函数的作用是根据表中字段进行分组,然后根据表中的字段排序;其实就是根据其排序顺序,给组中的每条记录添 加一个序号;且每组的序号都是从1开始,可利用它的这个特性进行分组…...

双向链表的实现(详解)

目录 前言初始化双向链表的结构为双向链表的节点开辟空间头插尾插打印链表尾删头删查找指定位置之后的插入删除pos节点销毁双向链表 前言 链表的分类&#xff1a; 带头 不带头 单向 双向 循环 不循环 一共有 (2 * 2 * 2) 种链表 带头指的是&#xff1a;带有哨兵位节点 哨兵位&a…...

SpringBoot项目中如何使用校验工具

用到hutool提供的校验方法与java提供的校验方法 1. 声明数据 String str "123" String regex "^123456$" Boolean is1_6 mismatch(str, regex);2. 定义校验方法 // 校验是否不符合正则格式 private static boolean mismatch(String str, String rege…...

AI预测小分子与蛋白的相关特征: MegaMolBART, MoFlow,ESM-1, ESM-2

1、小分子:MegaMolBART, MoFlow 1)MegaMolBART https://github.com/NVIDIA/MegaMolBART 基于 SMILES 的小分子药物发现与化学信息学深度学习模型。 2)MoFlow https://github.com/calvin-zcx/moflow 用flow流方式分子生成 2、蛋白质:ESM-1, ESM-2 https://github.com/fa…...

基于深度学习的花卉检测系统(含PyQt界面)

基于深度学习的花卉检测系统&#xff08;含PyQt界面&#xff09; 前言一、数据集1.1 数据集介绍1.2 数据预处理 二、模型搭建三、训练与测试3.1 模型训练3.2 模型测试 四、PyQt界面实现参考资料 前言 本项目是基于swin_transformer深度学习网络模型的花卉检测系统&#xff0c;…...

深度学习图像处理基础工具——opencv 实战信用卡数字识别

任务 信用卡数字识别 穿插之前学的知识点 形态学操作 模板匹配 等 总体流程与方法 1.有一个模板 2 用轮廓检测把模板中数字拿出来 外接矩形&#xff08;模板和输入图像的大小要一致 &#xff09;3 一系列预处理操作 问题的解决思路 1.分析准备&#xff1a;准备模板&#…...

【HBase】HBase高性能架构:如何保证大规模数据的高可用性

HBase高性能原理 HBase 能够提供高性能的数据处理能力&#xff0c;主要得益于其设计和架构的几个关键方面。这些设计特点使得 HBase 特别适合于大规模、分布式的环境中进行高效的数据读写操作。以下是 HBase 高性能的主要原因&#xff1a; 1. 基于列的存储 HBase 是一个列式…...

JAVA基础两个项目案例代码

1.JAVA使用ArrayList上架菜品案例 视频参考链接 创建一个Food.java类 package org.example;// 菜品类 public class Food {private String name; // 菜品名private double price; // 价格private String desc; // 菜品描述public Food() {}public Food(String name, Double …...

asp.net core 网页接入微信扫码登录

创建微信开放平台账号&#xff0c;然后创建网页应用 获取appid和appsecret 前端使用的vue&#xff0c;安装插件vue-wxlogin 调用代码 <wxlogin :appid"appId" :scope"scope" :redirect_uri"redirect_uri"></wxlogin> <scri…...

网站建设 软文/app怎么推广运营

定义&#xff1a; 注意&#xff1a; 这个二叉树就不是二叉树&#xff0c;因为它的第10个结点没有靠左对齐 **二叉树的性质 重要 第二页的性质在讲二叉堆的时候还会用到...

开源网站系统/网站关键词排名分析

作者 | 屠敏出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09;日前&#xff0c;TIOBE 编程语言社区最新发布了 2019 年 5 月排行榜。和 4 月榜单相比&#xff0c;5 月编程语言排行榜的 Top 10 位置并没有太大变化。但是在 C 和 Python 激烈的竞争局势下&#xff0c;随…...

wordpress上传视频大小/站长工具怎么用

一、概述在正常细胞中&#xff0c;磷脂酰丝氨酸只分布在细胞膜脂质双层的内侧&#xff0c;细胞发生凋亡最早期&#xff0c;膜磷脂酰丝氨酸(PS)由脂膜内侧翻向外侧&#xff0c;这一变化早于细胞皱缩、染色质浓缩、DNA片断化和细胞膜的通透性增加等凋亡现象。AnnexinV是一种磷脂结…...

同ip多域名做网站/网站优化排名操作

swift 代码 object-c 代码 类比&#xff1a; 1.静态方法 2.强制转换类型 3.创建实例对象 4.随机数 5.播放声音资源如果不在&#xff0c;程序会在获取资源的code处 crash 转载于:https://www.cnblogs.com/madaha/p/4179499.html...

河北省建设工程招标投标协会网站/福州seo推广优化

在Apache RocketMQ中&#xff0c;NameServer旨在协调分布式系统的每个组件&#xff0c;并通过管理主题路由信息来履行大部分职责。大致来说&#xff0c;管理层由两部分组成:Broker定期更新元数据&#xff0c;包括他们拥有的topic&#xff0c;这些topic保存在每一个NameServer中…...

如何在网站中做公示信息/下载百度网盘app最新版

接上篇。。。 4. 可空属性&默认值&忽略属性 默认情况下, 属性值可空, 如果强制要求某个属性非空, 可以使用如下方法&#xff1a; 遵循协议方法 (NSArray *)requiredProperties { return ["name"]; } 特点&#xff1a;如果再次赋值为nil, 则会抛出异常错误 也…...