算法3:查找算法

news/2024/6/16 11:39:32/文章来源:https://blog.csdn.net/qq_55630615/article/details/137236344

查找算法

常用查找算法

1,顺序(线性)查找

2,二分查找/折半查找

3,插值查找

4,斐波那契查找

线性查找

线性查找,通过遍历和逐一比对,在发现相同值时返回下标

代码如下
public int Seqsearch(int t, int[] arr) {for (int i = 0; i < arr.length; i++) {if (t == arr[i]) {return i;}}return -1;
}

二分查找

只能对有序数组查找

使用递归进行二分查找

1,确定数组中间的下标

2,让需要查找的数字与mid进行比较,递归向左或者右进行查找

3,得到结果

代码如下
public int binarysearch(int t,int left,int right,int[] arr){int mid = (left+right)/2;if(left>right){return -1;}if(arr[mid]==t){return mid;}else if(arr[mid]>t){return binarysearch(t,left,mid-1,arr);//递归最终返回mid}else{return binarysearch(t,mid+1,right,arr);//递归最终返回mid}
}
升级二分查找

找到数组所有的符合条件元素(相同元素全部返回)

在找到元素后向其左右扫描,直到扫完全部相同元素,放入一个集合中

最后返回一个集合

插值查找

类似于二分查找,但插值查找每次从自适应mid处开始查找

插值索引公式:mid = low+(high-low)*(key-arr[low])/(arr[high]-arr[low])

即每次重新查找会根据上一次的mid值与所求值的差值大小占整个查找范围差值大小的比值进行查找

在分布均匀的数组中较为优势

eg:在一个0-100的数组中查找值,可以直接一次找到

代码如下
public int insertsearch(int t,int left,int right,int[] arr){if(t>right || t<left){return -1;}int mid = left+(right-left)*(t-arr[left])/(arr[right]-arr[left]);if(left>=right){return -1;}if(arr[mid]==t){return mid;}else if(arr[mid]>t){return insertsearch(t,left,mid-1,arr);}else{return insertsearch(t,mid+1,right,arr);}}

在不均匀的数据结构中,这个查找方法不一定有优势

斐波那契查找算法

斐波那契数列元素之间的比例无限接近于黄金分割值0.618

查找思路

原理来自于斐波那契数列中后项等于前两项的和

所以只要当数列长度等于斐波那契数列中的某一项,就可以按照斐波那契数列的比例无限分割,直到1为止

mid = low + F(k-1)-1

F代表斐波那契数列

将分割点放在黄金分割点附近

当数据结构长度不足斐波那契数列中某个元素的值时,需要进行补长

代码如下
// 辅助函数:生成斐波那契数列
private static int[] generateFibonacci(int n) {int[] fibonacci = new int[n];fibonacci[0] = 0;fibonacci[1] = 1;for (int i = 2; i < n; i++) {fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];}return fibonacci;
}// 斐波那契查找算法
public static int fibonacciSearch(int[] arr, int key) {int n = arr.length;// 生成斐波那契数列,找到最接近且大于等于 n 的值int[] fibonacci = generateFibonacci(n);int k = 0;while (fibonacci[k] < n) {k++;}// 将数组扩展到斐波那契数列的长度int[] temp = new int[fibonacci[k]];System.arraycopy(arr, 0, temp, 0, n);int low = 0;int high = n - 1;// 主要查找过程while (low <= high) {int mid = low + fibonacci[k - 1] - 1;if (key < temp[mid]) {high = mid - 1;k -= 1;} else if (key > temp[mid]) {low = mid + 1;k -= 2;} else {// 找到了目标元素,需要判断返回的是原数组中的索引还是扩展数组中的索引return Math.min(mid, high);}}// 未找到目标元素return -1;
}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};int key = 7;int result = fibonacciSearch(arr, key);if (result != -1) {System.out.println("元素 " + key + " 在数组中的索引为:" + result);} else {System.out.println("元素 " + key + " 不在数组中");}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1033554.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【opencv】教程代码 —features2D(7)根据单应性矩阵估计相机坐标系下的物体位姿...

pose_from_homography.cpp从图像中找到棋盘角点并进行姿态估计 从图像中找到棋盘角点并显示 计算角点在世界坐标系中的位置 读取相机内参和畸变系数并校正图像中的角点 计算从3D点到2D点的单应性矩阵 通过奇异值分解(SVD)优化对旋转矩阵的估计 基于单应矩阵分解及其优化结果&am…

HarmonyOS 应用开发之LifecycleForm接口切换LifecycleApp接口切换 LifecycleApp接口切换

LifecycleForm接口切换 FA模型接口Stage模型接口对应d.ts文件Stage模型对应接口onCreate?(want: Want): formBindingData.FormBindingData;ohos.app.form.FormExtensionAbility.d.tsonAddForm(want: Want): formBindingData.FormBindingData;onCastToNormal?(formId: string…

Java复习第十一天学习笔记(IO流),附有道云笔记链接

【有道云笔记】十一 3.27 IO流 https://note.youdao.com/s/PeEdd3Zo 一、IO介绍以及分类 IO: Input Output 流是一组有顺序的&#xff0c;有起点和终点的字节集合&#xff0c;是对数据传输的总称或抽象。即数据在两设备间的传输称为流&#xff0c;流的本质是数据传输&#x…

无人机编队 | 基于自适应航迹评价函数权重的动态窗口法长机-僚机法实现多无人机路径规划附matlab代码

基本概述 实现基于自适应航迹评价函数权重的动态窗口法(Dynamic Window Approach, DWA)的长机-僚机(Leader-Follower)多无人机路径规划是一个复杂的任务,涉及到多个算法的组合与改进。这里我会简要介绍其原理,并提供一个基础的Matlab代码框架,但请注意,这只是一个起点…

如何恢复被.locked勒索病毒加密的服务器和数据库?

.locked勒索病毒有什么特点&#xff1f; .locked勒索病毒的特点主要包括以下几个方面&#xff1a; 文件加密&#xff1a;.locked勒索病毒会对受感染设备上的所有文件进行加密&#xff0c;包括图片、文档、视频和其他各种类型的重要文件。一旦文件被加密&#xff0c;文件的扩展…

Day14_学点CSS_高级选择器Demo

1 后代选择器s1 s2 <!--~ 适度编码益脑&#xff0c;沉迷编码伤身&#xff0c;合理安排时间&#xff0c;享受快乐生活。~ Copyright TangXJ~ Created by TangXJ~ Created&Used date: 2024/3/29 下午3:46 ~ 2024/3/29 下午3:47~ Modified date: 2024/3/29 下午3:47-->…

C语言 | Leetcode C语言题解之3题无重复字符的最长子串

题目&#xff1a; 题解&#xff1a; int lengthOfLongestSubstring(char * s) {//类似于hash的思想//滑动窗口维护int left 0;int right 0;int max 0;int i,j;int len strlen(s);int haveSameChar 0;for(i 0; i < len ; i ){if(left < right){ //检测是否出现重…

OpenHarmony实战开发-图案密码锁组件的使用

介绍 本示例展示了图案密码锁组件的使用&#xff0c;实现了密码设置、验证和重置功能。 图案密码锁组件&#xff1a;以宫格图案的方式输入密码&#xff0c;用于密码验证。手指触碰图案密码锁时开始进入输入状态&#xff0c;手指离开屏幕时结束输入状态并向应用返回输入的密码…

STM32学习和实践笔记(4): 分析和理解GPIO_InitTypeDef GPIO_InitStructure (b)

继续上篇博文&#xff1a;STM32学习和实践笔记&#xff08;4&#xff09;: 分析和理解GPIO_InitTypeDef GPIO_InitStructure (a)-CSDN博客 往下写&#xff0c; 为什么&#xff1a;当GPIO_InitStructure.GPIO_PinGPIO_Pin_0 ; 时&#xff0c;其实就是将对应的该引脚的寄存器地…

docker--部署 (超详版) (五)

环境准备&#xff1a;docker&#xff0c;mysql&#xff0c;redis&#xff0c;镜像&#xff0c;nginx 把虚拟机打开&#xff0c;连接xshell&#xff0c;参考博客&#xff1a; https://blog.csdn.net/m0_74229802/article/details/136965820?spm1001.2014.3001.5501 一&#x…

HCIP作业4

实验步骤&#xff1a; 第一步 给PC1和PC2和PC3配地址 第二步给R1到R5配置接口IP地址 [R1]int g0/0/0 [R1-GigabitEthernet0/0/0]ip ad 192.168.1.254 24 R1&#xff1a;[R1-GigabitEthernet0/0/0]int s4/0/0 [R1-Serial4/0/0]ip ad 15.1.1.1 24 [R1-Serial4/0/0]dis ip in…

Flutter 开发学习笔记(0):环境配置

文章目录 前言开发需求环境配置运行出现问题我运行也是解决了很久的问题镜像源设置为清华的镜像源&#xff08;不知道有没有影响&#xff09;使用JDK17&#xff0c;测试过JDK21和JDK11都不行手动下载flutter 对应的gradle添加阿里云代理安卓编译下载 运行成功&#xff01; 前言…

基于Springboot的一站式家装服务管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的一站式家装服务管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体…

2024年MathorCup数学建模思路A题B题C题D题思路分享

文章目录 1 赛题思路2 比赛日期和时间3 组织机构4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间&#xff1a;2024…

css设置文字铺满盒子

<div>收货人</div>&#xff1a; <div>电话</div>&#xff1a; <div>省市区</div>&#xff1a; width: 100rpx;border: 1px solid rebeccapurple;display: inline-block;text-align-last: justify;

构建安全高效的用户登录系统:登录流程设计与Token验证详解

在当今数字化时代&#xff0c;用户登录系统是几乎所有在线服务的基础。然而&#xff0c;随着网络安全威胁的不断增加&#xff0c;设计一个安全可靠的登录系统变得至关重要。本文将深入探讨用户登录流程的设计原则以及Token验证的实现方式&#xff0c;带您了解如何构建安全高效的…

网络安全新视角:数据可视化的力量

在当今数字化时代&#xff0c;网络安全已成为各大企业乃至国家安全的重要组成部分。随着网络攻击的日益复杂和隐蔽&#xff0c;传统的网络安全防护措施已难以满足需求&#xff0c;急需新型的解决方案以增强网络防护能力。数据可视化技术&#xff0c;作为一种将复杂数据转换为图…

代码+视频,手动绘制logistic回归预测模型校准曲线(Calibration curve)(1)

校准曲线图表示的是预测值和实际值的差距&#xff0c;作为预测模型的重要部分&#xff0c;目前很多函数能绘制校准曲线。 一般分为两种&#xff0c;一种是通过Hosmer-Lemeshow检验&#xff0c;把P值分为10等分&#xff0c;求出每等分的预测值和实际值的差距. 另外一种是calibra…

基于Websocket的局域网聊天系统

1.1 研究背景及意义 本项目所对应领域的研究背景及意义[1]。新冠肺炎局域网通信发生以来&#xff0c;大数据、云计算、人工智能等新一代信息技术加速与交通、局域网通信、教育、金融等领域深度融合&#xff0c;让局域网通信防控的组织和执行更加高效&#xff0c;成为战“疫”的…

【三】EMQX 手动创建集群

EMQX 手动创建集群 简介 因为项目中使用到了emqx中间件&#xff0c;所以近期对中间件进行了进一步的研究&#xff0c;每次选用中间件我都会考虑可用性方案&#xff0c;如下是本地实践的记录。 一、部署 1、创建一个 Docker 网络&#xff0c;用于节点间通信。处于同一网络下的…