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

Java查找算法知识点(含面试大厂题和源码)

查找算法是计算机科学中的基础概念,它们在解决实际问题时扮演着关键角色。了解和掌握不同的查找算法,能够帮助我们更高效地处理数据检索任务。以下是一些关于查找算法的关键知识点:

  1. 算法分类

    • 线性查找算法:按照顺序逐个检查元素,直到找到目标或遍历完毕。
    • 二分查找算法:在有序集合中使用,通过不断缩小搜索范围来查找目标元素。
    • 插值查找算法:适用于均匀分布的有序集合,通过预测目标元素的位置来加快查找速度。
    • 哈希查找算法:使用哈希表进行查找,通过哈希函数将关键字映射到表中一个位置。
    • 树形查找算法:如二叉搜索树、B树、B+树等,通过树形结构来组织数据,加快查找速度。
  2. 时间复杂度

    • 线性查找的时间复杂度为 O(n)。
    • 二分查找的时间复杂度为 O(log n)。
    • 插值查找在最理想情况下可以达到 O(log log n),但在最坏情况下会退化为 O(n)。
    • 哈希查找的理想时间复杂度为 O(1),但在处理哈希冲突时可能退化为 O(n)。
    • 树形查找算法的时间复杂度依赖于树的高度,平衡树形结构的平均时间复杂度为 O(log n)。
  3. 空间复杂度

    • 线性查找不需要额外空间或只需要常数级别的额外空间。
    • 二分查找和插值查找的空间复杂度为 O(1)。
    • 哈希查找的空间复杂度取决于哈希表的大小和装填因子。
    • 树形查找算法的空间复杂度取决于树的高度和节点的分支数。
  4. 适用场景

    • 线性查找适用于小型数据集或无序数据集。
    • 二分查找和插值查找适用于大型的有序数据集。
    • 哈希查找适用于无序数据集,且查询操作非常频繁的场景。
    • 树形查找算法适用于处理大量数据,并且需要频繁插入、删除和查找操作的场景。
  5. 优化策略

    • 对于线性查找,可以通过减少数据集的大小或改进数据存储结构来优化。
    • 二分查找和插值查找的优化通常涉及到如何选择一个好的有序数组或如何设计一个高效的哈希函数。
    • 哈希查找的优化通常涉及到如何处理哈希冲突,例如开放寻址法、链地址法等。
    • 树形查找算法的优化通常涉及到如何保持树的平衡,例如 AVL 树、红黑树等。
  6. 哈希冲突

    • 哈希冲突是指两个或多个不同的关键字产生相同的哈希值。
    • 解决哈希冲突的方法包括开放寻址法、链地址法、再散列法等。
  7. 动态查找

    • 动态查找是指在查找过程中动态地更新查找表,包括插入、删除和修改操作。

掌握这些查找算法的知识点,可以帮助我们在面对不同的数据检索问题时,选择最合适的算法来解决问题。在实际应用中,算法的选择往往需要综合考虑时间复杂度、空间复杂度、数据的特点和操作的频率等因素。查找算法是计算机科学中的一类算法,用于在数据结构中查找特定的元素或者满足特定条件的元素。查找算法的效率对于程序的整体性能有着重要的影响。以下是几种常见的查找算法,以及它们的基本原理和适用场景。

1. 线性查找(Linear Search)

基本原理:线性查找是最简单的查找算法。它从数据结构的一端开始,逐个检查每个元素,直到找到目标元素或者遍历完整个数据结构。

时间复杂度:O(n),其中 n 是数据结构中元素的数量。

适用场景:适用于无序数据集的查找,或者数据量较小的情况下。

Java 示例

public static int linearSearch(int[] array, int target) {for (int i = 0; i < array.length; i++) {if (array[i] == target) {return i;}}return -1; // 表示未找到目标元素
}

2. 二分查找(Binary Search)

基本原理:二分查找是一种在有序数据集上进行的查找算法。它每次将数据集分为两部分,并比较中间元素与目标值,根据比较结果决定是继续在左侧子集查找还是右侧子集查找。

时间复杂度:O(log n)。

适用场景:适用于有序数据集的查找,效率较高。

Java 示例

public static int binarySearch(int[] array, int target) {int left = 0;int right = array.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (array[mid] == target) {return mid;} else if (array[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 表示未找到目标元素
}

3. 插值查找(Interpolation Search)

基本原理:插值查找是二分查找的一种改进,适用于数据分布均匀的有序数据集。它根据目标值在数据集中的估计位置来查找,而不是简单地每次都将数据集分为两部分。

时间复杂度:在数据分布均匀的情况下,平均时间复杂度为 O(log log n)。

适用场景:适用于数据量大且分布均匀的有序数据集。

Java 示例

public static int interpolationSearch(int[] array, int target) {int left = 0;int right = array.length - 1;while (left <= right && target >= array[left] && target <= array[right]) {int pos = left + ((target - array[left]) * (right - left)) / (array[right] - array[left]);if (array[pos] == target) {return pos;}if (array[pos] < target) {left = pos + 1;} else {right = pos - 1;}}return -1; // 表示未找到目标元素
}

4. 哈希查找(Hash Search)

基本原理:哈希查找是通过哈希表进行的查找算法。它通过哈希函数将关键字映射到哈希表的一个位置,从而实现快速查找。

时间复杂度:理想情况下为 O(1),但在哈希冲突的情况下可能退化为 O(n)。

适用场景:适用于无序数据集的快速查找,特别是当数据量很大时。

Java 示例

import java.util.HashMap;
import java.util.Map;public static int hashSearch(Map<Integer, Integer> map, int target) {return map.containsKey(target) ? map.get(target) : -1; // 表示未找到目标元素
}// 示例用法
Map<Integer, Integer> map = new HashMap<>();
// 假设 map 已经被填充了数据
int result = hashSearch(map, targetValue);

以上是几种常见的查找算法,它们各有优势和适用场景。在实际应用中,选择合适的查找算法可以显著提高程序的查找效率。

相关文章:

Java查找算法知识点(含面试大厂题和源码)

查找算法是计算机科学中的基础概念&#xff0c;它们在解决实际问题时扮演着关键角色。了解和掌握不同的查找算法&#xff0c;能够帮助我们更高效地处理数据检索任务。以下是一些关于查找算法的关键知识点&#xff1a; 算法分类&#xff1a; 线性查找算法&#xff1a;按照顺序逐…...

67、yolov8目标检测和旋转目标检测算法部署Atlas 200I DK A2开发板上

基本思想&#xff1a;需求部署yolov8目标检测和旋转目标检测算法部署atlas 200dk 开发板上 一、转换模型 链接: https://pan.baidu.com/s/1hJPX2QvybI4AGgeJKO6QgQ?pwdq2s5 提取码: q2s5 from ultralytics import YOLO# Load a model model YOLO("yolov8s.yaml")…...

A Little Is Enough: Circumventing Defenses For Distributed Learning

联邦学习的攻击方法&#xff1a;LIE 简单的总结&#xff0c;只是为了能快速想起来这个方法。 无目标攻击 例如总共50个客户端&#xff0c;有24个恶意客户端&#xff0c;那么这个时候&#xff0c;他需要拉拢2个良性客户端 计算 50 − 24 − 2 50 − 24 0.923 \frac{50-24-2}{…...

文心一言 VS 讯飞星火 VS chatgpt (225)-- 算法导论16.3 7题

七、推广赫夫曼算法&#xff0c;使之能生成三进制的码字(即码字由符号0、1、2组成)&#xff0c;并证明你的算法能生成最优三进制码。如果要写代码&#xff0c;请用go语言。 文心一言&#xff1a; 推广赫夫曼算法以生成三进制码字需要对算法进行一定的修改&#xff0c;确保在每…...

【计算机】——51单片机——持续更新

单片机是一种内部包含CPU、存储器和输入/输出接口等电路的集成电路&#xff08;IC芯片&#xff09; 单片机是单片微型计算机&#xff08;Single Chip Microcomputer&#xff09;的简称&#xff0c;用于控制领域&#xff0c;所以又称为微型控制器&#xff08;Microcontroller U…...

QT资源添加调用

添加资源文件&#xff0c;新建资源文件夹&#xff0c;命名resource&#xff0c;然后点下一步&#xff0c;点完成 资源&#xff0c;右键add Prefix 添加现有文件 展示的label图片切换 QLabel *led_show; #include "mainwindow.h" #include<QLabel> #include&l…...

LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】

LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】 题目描述&#xff1a;解题思路一&#xff1a;哈希表和排序&#xff0c;这里最关键的点是&#xff0c;乱序单词的排序结果必然是一样的&#xff08;从而构成哈希表的key&#xff09;。解题思路二&#xff1a;解题思路三…...

绘制特征曲线-ROC(Machine Learning 研习十七)

接收者操作特征曲线&#xff08;ROC&#xff09;是二元分类器的另一个常用工具。它与精确度/召回率曲线非常相似&#xff0c;但 ROC 曲线不是绘制精确度与召回率的关系曲线&#xff0c;而是绘制真阳性率&#xff08;召回率的另一个名称&#xff09;与假阳性率&#xff08;FPR&a…...

.Net 知识杂记

记录平日中琐碎的.net 知识点。不定期更新 目标框架名称(TFM) 我们创建C#应用程序时&#xff0c;在项目的工程文件(*.csproj)中都有targetFramework标签&#xff0c;以表示项目使用的目标框架 各种版本的TFM .NET Framework .NET Standard .NET5 及更高版本 UMP等 参考文档&a…...

海豚【货运系统源码】货运小程序【用户端+司机端app】源码物流系统搬家系统源码师傅接单

技术栈&#xff1a;前端uniapp后端vuethinkphp 主要功能&#xff1a; 不通车型配置不通价格参数 多城市定位服务 支持发货地 途径地 目的地智能费用计算 支持日期时间 预约下单 支持添加跟单人数选择 支持下单优惠券抵扣 支持司机收藏订单评价 支持订单状态消息通知 支…...

01---java面试八股文——mybatis-------10题

1、什么是MyBatis Mybatis是一个半ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;它内部封装了JDBC&#xff0c;开发时只需要关注SQL语句本身&#xff0c;不需要花费精力去处理加载驱动、创建连接、创建statement等繁杂的过程。程序员直接编写原生态sql&#xff0c…...

增强现实(AR)的开发工具

增强现实&#xff08;AR&#xff09;的开发工具涵盖了一系列的软件和平台&#xff0c;它们可以帮助开发者创造出能够将虚拟内容融入现实世界的应用程序。以下是一些在AR领域内广泛使用的开发工具。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎…...

用Unity制作正六边形拼成的地面

目录 效果演示 1.在Unity中创建正六边形 2.创建一个用于管理正六边形的类 3.创建一个用于管理正六边形地面的类 4.创建一个空对象并将游戏控制脚本挂上 5.设置正六边形碰撞所需组件 6.创建正六边形行为触发脚本并挂上 7.创建圆柱体——田伯光 8.创建圆柱体移动脚本 运…...

Spark部署详细教程

Spark Local环境部署 下载地址 https://dlcdn.apache.org/spark/spark-3.4.2/spark-3.4.2-bin-hadoop3.tgz 条件 PYTHON 推荐3.8JDK 1.8 Anaconda On Linux 安装 本次课程的Python环境需要安装到Linux(虚拟机)和Windows(本机)上 参见最下方, 附: Anaconda On Linux 安装…...

慧天[HTWATER]:创新城市水务科技,引领行业变革

【城市内涝水文水动力模型介绍】 慧天[HTWATER]软件&#xff1a;慧天排水数字化分析平台针对城市排水系统基础设施数据管理的需求&#xff0c;以及水文、水力及水质模拟对数据的需求&#xff0c;实现了以数据库方式对相应数据的存储。可以对分流制排水系统及合流制排水系统进行…...

vscode调试Unity

文章目录 vscode调试UnityC#环境需求开始调试 Lua添加Debugger环境配置联系.txt文件配置Java环境 添加调试代码断点不生效的问题 vscode调试Unity C# 现在使用vscode调试Unity的C#代码很简单&#xff0c;直接在vscode的EXTENSIONS里面搜索“Unity”&#xff0c;第一个就是&am…...

JavaScript是如何实现页面渲染的

JavaScript实现页面渲染主要涉及到对DOM的操作、样式的修改以及与后端数据的交互。以下是JavaScript实现页面渲染的主要步骤和方式&#xff1a; 一、DOM操作 创建和修改元素&#xff1a;JavaScript可以使用document.createElement()来创建新的DOM元素&#xff0c;使用appendC…...

【YOLOv8 代码解读】数据增强代码梳理

1. LetterBox增强 当输入图片的尺寸和模型实际接收的尺寸可能不一致时&#xff0c;通常需要使用LetterBox增强技术。具体步骤是先将图片按比例缩放&#xff0c;将较长的边缩放到设定的尺寸以后&#xff0c;再将较短的边进行填充&#xff0c;最终短边的长度为stride的倍数即可。…...

安卓调试桥ADB

Logcat 命令行工具 | Android Studio | Android Developers 什么是ADB ADB 全称为 Android Debug Bridge &#xff0c;是 Android SDK &#xff08;安卓的开发工具&#xff09;中的一个工具&#xff0c;起到调试桥的作用&#xff0c;是一个 客户端 - 服务器端程序 。其中 …...

深入理解数据结构第一弹——二叉树(1)——堆

前言&#xff1a; 在前面我们已经学习了数据结构的基础操作&#xff1a;顺序表和链表及其相关内容&#xff0c;今天我们来学一点有些难度的知识——数据结构中的二叉树&#xff0c;今天我们先来学习二叉树中堆的知识&#xff0c;这部分内容还是非常有意思的&#xff0c;下面我们…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...