关键词:
🍅 作者主页:Roninaxious
🍅 欢迎点赞 👍 收藏 ⭐留言 📝
🍅 话不多说 🍁开卷!
🚢 顺序查找算法
🙄对于顺序查找算法比较容易理解,遍历一个数组即可,如果找到该值返回对应的下标即可.🙄
🧧源代码🧧
/**
* 如果返回的是-1,则数组中无相关值
* @param arr 待搜索数组
* @param value 待搜索值
* @return -1或者 索引值
*/
private static int seqSearch(int[] arr, int value)
for (int i = 0; i < arr.length; i++)
if (arr[i] == value) //如果找到对应的值
return i; //返回对应的索引
return -1; //没有找到返回-1
🎐测试代码🎐
public static void main(String[] args)
int[] arr = 1, 34, -1, 5, 8, 2, 99;
int index = seqSearch(arr, 8);
if (index == -1)
System.out.println("无相关值!");
else
System.out.println("改值对应的索引下标为:"+index);
🚢 二分查找算法
🙄对于某一个数组arr(这个数组是有序的,假设是升序),我们想要从数组中找到值value,返回它对应得索引
begin = 0;
end = arr.length
mid = (begin+end)/2
这三个变量begin、mid、end对应这数组的下表
1.我们将value与arr[mid]进行比较
2.如果value > arr[mid],那么我们只需要在mid的右边进行搜索即可;如果value < arr[mid],我们只需要在mid的左边进行搜索即可.
🙄
🎐注意点🎐
Ⅰ.如果数组不是有序的,则需要将其进行排序后再操作
Ⅱ.使用递归能够很好实现
二分查找需要一定的递归知识
【☀️爆肝万字总结递归❤️玩转算法系列之我如何才能掌握递归解题的能力❤️十大经典问题助你突破极限☀️】:https://blog.csdn.net/Kevinnsm/article/details/120445071?spm=1001.2014.3001.5501
🧧源代码🧧
/**
*二分查找算法
* @param arr 待搜索的数组
* @param value 待查找的值
* @param begin 左边的索引
* @param end 右边的索引
* @return 如果找到该值,就返回其对应的下标,否者返回其-1
*/
private static int binarySearch(int[] arr, int value, int begin, int end)
if (begin > end)
return -1;
int mid = (begin + end) / 2; //取中间值
if (value > arr[mid])
return binarySearch(arr, value, mid + 1, end);
else if (value < arr[mid])
return binarySearch(arr, value, begin, mid - 1);
else
return mid;
🎐测试代码🎐
public static void main(String[] args)
int[] arr = 1,3, 4, 5, 8, 11, 23, 77;
int index = binarySearch(arr, 8, 0, arr.length - 1);
if (index == -1)
System.out.println("未找到该值!");
else
System.out.println(index);
💥优化二分查找算法
❤️如果一个数组是[1,2,4,5,6,8,8,8,8,11,23],一旦查找其他的8,那么如果使用上面的查找算法,就只能返回一个索引值;因此,对该查找算法进行优化,让其能够返回所有的索引值❤️
/**
* 默认是升序数组
* 对上部分进行优化,能够查出重复数据的所有下表
* @param arr 待搜索数组
* @param value 待查询的值
* @param begin 左索引
* @param end 右索引
* @param list 存储搜索值下表的集合
*/
private static void binarySearch2(int[] arr, int value, int begin, int end, List<Integer> list)
if (begin > end) //递归结束条件
return;
int mid = (begin + end) / 2; //取中值
if (value > arr[mid]) //说明需要去mid右边查找
binarySearch2(arr, value, mid + 1, end, list); //递归进入 mid+1 至 end这一段数据
else if (value < arr[mid]) //说明需要去mid左边查找
binarySearch2(arr, value, begin, mid - 1, list); //递归进入 begin 至 mid-1这一段数据
else if (value == arr[mid]) //说明找到了待查找的值;此时需要考虑的是在这个值的左边和右边可能有相同的数据
int tempFront = mid - 1; //例如arr [1,8,8,8,9],找到arr[2],它的前后都有8,所以需要进行判断
while (true) //这个while循环是对arr[2]左边进行判断是否有8
if (tempFront < 0 || value != arr[tempFront]) //这当上面的mid为0时,这个tempFront为-1,所以需要进行判断
break; //又或者左边第一个就不等于value,那么直接break即可
list.add(tempFront); //将符合value=8的索引值加入到list集合中
tempFront--;
list.add(mid); //将arr[2]加入到集合中,至于为什么现在加入是因为按照从大到小 list[2,3,4]
int tempAfter = mid + 1;
while (true) //右边类似于左边
if (tempAfter > end || value != arr[tempAfter])
break;
list.add(tempAfter);
tempAfter++;
🎐测试代码🎐
public static void main(String[] args)
int[] arr = 1,3, 4, 5, 5, 5, 5, 11, 23, 77;
List<Integer> list = new ArrayList<>();
binarySearch2(arr, 5, 0, arr.length - 1, list);
if (list.isEmpty())
System.out.println("未找到该值!");
else
System.out.println(list.toString());
🥫分析以上的二分查找算法
根据它的 int mid = (begin+end)/2 ,我们可以推算二分算法适用于什么场景;
假设一个数组为arr[1,2,3,4,5…,98,99,100] ,我们要找寻1这个值,那么需要几次找到呢?看下面的运行结果
可以看出经历了六次循环调用才找到;如果我们找value=50,那么一次就能成功!所以这个调用多少次与mid的取值也有很大关系;
分析mid=(begin+end)/2,看出begin、end无法做出改变,那么只有对1/2进行改动;mid=(begin+end) / (value-arr[begin])/(arr[end]-arr[begin]),根据上文中找寻1,我们可以算出mid = 1,所以一步就能找到;这就是下文提到的插值查找
🚢 插值查找算法
根据上文进行分析,这个插值查找算法是对二分查找算法的改进。
mid=(begin+end) / (value-arr[begin]) / (arr[end]-arr[begin])
☸下面这段源代码除了mid求的不一样之外,其他一模一样。☸
/**
* 自适应求出mid
* @param arr 待搜索数组
* @param value 待查询的值
* @param begin 左索引
* @param end 右索引
* @param list 存储搜索值下表的集合
*/
private static void interpolationSearch(int[] arr, int value, int begin, int end, List<Integer> list)
System.out.println("test");
//这个value要进行判断是否小于arr[0],否者在下面求mid时会报错
if (begin > value || value < arr[0] || value > arr.length - 1)
return;
int mid = (begin + end) * (value - arr[begin]) / (arr[end] - arr[begin]);
if (value > arr[mid])
interpolationSearch(arr, value, mid + 1, end, list);
else if (value < arr[mid])
interpolationSearch(arr, value, begin, mid - 1, list);
else if (value == arr[mid])
int tempFront = mid - 1;
while (true)
if (tempFront < 0 || value != arr[tempFront])
break;
list.add(tempFront);
tempFront--;
list.add(mid);
int tempAfter = mid + 1;
while (true)
if (tempAfter > end || value != arr[tempAfter])
break;
list.add(tempAfter);
tempAfter++;
根据数组为arr[1,2,3,4,5…,98,99,100] ,查找其中的1,只需一次便能查到.
🚢 斐波那契查找算法
…
❤️爆肝万字!一文最全总结之spring从入门到入土❤️(建议收藏)(代码片段)
文章目录最新更新前言1.Spring概述1.1介绍2.IoC入门2.1什么是IoC2.2IoC入门案例1(基础案例)2.3IoC入门案例2(依赖注入)2.4IoC入门案例3(面向接口编程)2.5IoC入门案例4(整合JUnit4)3.IoC详解3.1Bean的创建... 查看详情
❤️爆肝万字!一文最全总结之spring从入门到入土❤️(建议收藏)(代码片段)
文章目录前言1.Spring概述1.1介绍2.IoC入门2.1什么是IoC2.2IoC入门案例1(基础案例)2.3IoC入门案例2(依赖注入)2.4IoC入门案例3(面向接口编程)2.5IoC入门案例4(整合JUnit4)3.IoC详解3.1Bean的创建3.2依赖注... 查看详情
熬夜爆肝万字c#基础入门大总结建议收藏(代码片段)
...青铜到王者-开发效率插件篇点击跳转=>Unity粒子特效系列-龙卷风预制体做好了,unitypackage包直接用!点击跳转= 查看详情
❤️爆肝万字整理的综合架构web服务之nginx详解❤️,附建议收藏(代码片段)
文章目录nginx服务配置详细介绍关于作者前言一、nginxweb入门简介1.1什么是nginx1.2常见的网站服务1.3nginx网站服务特点1.4网站页面访问原理二、nginx服务部署安装2.1实验环境2.2YUM安装2.3源码编译安装2.4nginx重要文件目录结构2.5虚拟主... 查看详情
pythonopencv实战画图——这次一定能行!爆肝万字,建议点赞收藏~❤️❤️❤️(代码片段)
📢📢📢📣📣📣🌻🌻🌻Hello,大家好我叫是Dream呀,一个有趣的Python博主,小白一枚,多多关照😜😜😜🏅🏅 查看详情
❤️大学三年沉淀,把我的学习经验分享给你,爆肝万字带你走进编程世界!❤️(代码片段)
Hello,大家好,我是Alex。时光匆匆,暑假过的很快,转眼又到了大学的开学季,我也是又混进了我们学院的新生群,发现大家对计算机充满着迷之向往,啊哈哈哈,不过没有人带着入门还是很容易... 查看详情
(大厂必备)厂长熬夜爆肝万字之多线程高并发juc编程⭐学妹已收藏(代码片段)
🔥(大厂必备)厂长熬夜爆肝万字之多线程高并发JUC编程(一)⭐学妹已收藏❤️大家好,我是java厂长,今天带你们体验一把多线程高并发的面试高频!❤️关于作者作者介绍🍓博客主页:作者主页🍓... 查看详情
(大厂必备)厂长熬夜爆肝万字之多线程高并发juc编程⭐学妹已收藏(代码片段)
🔥(大厂必备)厂长熬夜爆肝万字之多线程高并发JUC编程(二)⭐学妹已收藏❤️大家好,我是java厂长,今天再次带你们体验一把多线程高并发的面试高频!❤️关于作者作者介绍🍓博客主页:作者主页... 查看详情
❤️3万字《算法+数据结构》刷了3333道算法题后的一点总结❤️(建议收藏)
文章目录1️⃣前言:追忆我的刷题经历2️⃣算法和数据结构的重要性👪1、适用人群🎾2、有何作用📜3、算法简介🌲4、数据结构3️⃣如何开始持续的刷题📑1、立军令状👩❤️👩2、培养兴... 查看详情
❤️3万字《算法+数据结构》刷了3333道算法题后的一点总结❤️(建议收藏)
文章目录1️⃣前言:追忆我的刷题经历2️⃣算法和数据结构的重要性👪1、适用人群🎾2、有何作用📜3、算法简介🌲4、数据结构3️⃣如何开始持续的刷题📑1、立军令状👩❤️👩2、培养兴... 查看详情
javascript之爆肝汇总万字长文❤值得收藏(代码片段)
目录一、JavaScript简单入门1.1.一门客户端脚本语言1.2.JavaScript发展史1.3.JavaScript优势1.4.JavaScript引用1.5.JavaScript输出的几种方式1.6.JavaScript有哪些关键字1.7.JavaScript注释1.8.JavaScript常见标识符有哪些1.9.JavaScript常见HTML事件有哪些1.10.Jav... 查看详情
熬夜爆肝万字c#基础入门大总结建议收藏(代码片段)
...青铜到王者-开发效率插件篇点击跳转=>Unity粒子特效系列-龙卷风预制体做好了,unitypackage包直接用!点击跳转=>姐姐喊我解锁套娃新技能:FairyGUI在Unity中实现List嵌套List/立体画廊等,玩出花儿来点击跳... 查看详情
❤️爆肝四万字的mysql总结全面整理+详细解释❤️(代码片段)
文章目录1.初识MySQL1.2数据库分类1.3MySQL简介1.4MySQL安装1.5MySQL(压缩包)安装配置1.6SQLyog使用的注意事项1.7连接数据库和一些基本命令2.操作数据库2.1操作数据库2.2数据库的数据类型(列类型)2.3数据库的字段属性2.4创建数据库表(... 查看详情
爆肝一周面试10多家中大厂后的万字总结——❤️javaweb篇❤️(建议收藏)(代码片段)
⭐欢迎订阅《大厂面试突击》专栏,面试10多家大厂总结出的高频面试知识,免费阶段大家赶快订阅⭐更多精品专栏简介点这里⭐更多大厂全路线学习视频+笔记,PC端看左侧「关于作者」,手机端「私信」博主... 查看详情
中秋节爆肝万字,带你熟悉linux进程的基本操作!!!(代码片段)
今天是中秋节,祝各位小伙伴中秋节快乐,记得吃月饼吖图片来自网络,侵联删Linux进程基本操作1.进程基本概念在Linux中进程信息被保存在task_struct(PCB)2.查看进程的方法pspsaux|greapmyprocls/proc3.创建进程fork():创建一个子进程#i... 查看详情
中秋节爆肝万字,带你熟悉linux进程的基本操作!!!(代码片段)
今天是中秋节,祝各位小伙伴中秋节快乐,记得吃月饼吖图片来自网络,侵联删Linux进程基本操作1.进程基本概念在Linux中进程信息被保存在task_struct(PCB)2.查看进程的方法pspsaux|greapmyprocls/proc3.创建进程fork():创建一个子进程#i... 查看详情
❤️爆肝六万字最全总结java数据库编程mybatis(建议收藏)(代码片段)
前言今天复习Java数据库编程,二话不说MyBatis手把手保姆级教程献上,再也不用担心学不会!资料:链接:https://pan.baidu.com/s/1FIDi_9QiTuhb4x7pksGOUQ提取码:kevf1.MyBatis入门文章目录前言1.MyBatis入门1.1概述1.2下载1.3与JDBC对比1.4入门案... 查看详情
❤️爆肝六万字最全总结java数据库编程mybatis(建议收藏)(代码片段)
前言今天复习Java数据库编程,二话不说MyBatis手把手保姆级教程献上,再也不用担心学不会!资料:链接:https://pan.baidu.com/s/1FIDi_9QiTuhb4x7pksGOUQ提取码:kevf1.MyBatis入门文章目录前言1.MyBatis入门1.1概述1.2下载1.3与JDBC对比1.4入门案... 查看详情