算法系列15天速成——第四天 五大经典查找【上】
在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都是查找。
在我们的算法中,有一种叫做线性查找。
分为:顺序查找。
折半查找。
查找有两种形态:
分为:破坏性查找, 比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。
哥不找23+的,所以此种查找破坏了原来的结构。
非破坏性查找, 这种就反之了,不破坏结构。
顺序查找:
这种非常简单,就是过一下数组,一个一个的比,找到为止。
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace Sequential
7 {
8 class Program
9 {
10 static void Main(string[] args)
11 {
12 List<int> list = new List<int>() { 2, 3, 5, 8, 7 };
13
14 var result = SequenceSearch(list, 3);
15
16 if (result != -1)
17 Console.WriteLine("3 已经在数组中找到,索引位置为:" + result);
18 else
19 Console.WriteLine("呜呜,没有找到!");
20
21 Console.Read();
22 }
23
24 //顺序查找
25 static int SequenceSearch(List<int> list, int key)
26 {
27 for (int i = 0; i < list.Count; i++)
28 {
29 //查找成功,返回序列号
30 if (key == list[i])
31 return i;
32 }
33 //未能查找,返回-1
34 return -1;
35 }
36 }
37 }
折半查找: 这种查找很有意思,就是每次都砍掉一半,
比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,
那结果是相当的啊。
不过要注意,这种查找有两个缺点:
第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。
第二: 这种查找只限于线性的顺序存储结构。
上代码:
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace BinarySearch
7 {
8 class Program
9 {
10 static void Main(string[] args)
11 {
12 List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };
13
14 var result = BinarySearch(list, 45);
15
16 if (result != -1)
17 Console.WriteLine("45 已经在数组中找到,索引位置为:" + result);
18 else
19 Console.WriteLine("呜呜,没有找到!");
20
21 Console.Read();
22 }
23
24 ///<summary>
25 /// 折半查找
26 ///</summary>
27 ///<param name="list"></param>
28 ///<returns></returns>
29 public static int BinarySearch(List<int> list, int key)
30 {
31 //最低线
32 int low = 0;
33
34 //最高线
35 int high = list.Count - 1;
36
37 while (low <= high)
38 {
39 //取中间值
40 var middle = (low + high) / 2;
41
42 if (list[middle] == key)
43 {
44 return middle;
45 }
46 else
47 if (list[middle] > key)
48 {
49 //下降一半
50 high = middle - 1;
51 }
52 else
53 {
54 //上升一半
55 low = middle + 1;
56 }
57 }
58 //未找到
59 return -1;
60 }
61 }
62 }
先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,
可能都导致数组元素的整体前移或后移。
所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。
ps: 线性查找时间复杂度:O(n);
折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);
折半有序的时间复杂度:O(logN);
相关文章
- 【Spring专题】「开发指南」夯实实战基础功底之解读logback-spring.xml文件的详解实现
- 精华推荐 |【深入浅出Sentinel原理及实战】「原理探索专题」完整剖析Alibaba微服务架构体系之轻量级高可用流量控制组件Sentinel(1)
- 【深入浅出Spring原理及实战】「源码原理实战」从底层角度去分析研究PropertySourcesPlaceholderConfigurer的原理及实战注入机制
- 精华推荐 | 【深入浅出RocketMQ原理及实战】「性能原理挖掘系列」透彻剖析贯穿RocketMQ的事务性消息的底层原理并在分析其实际开发场景
- 深度剖析 | 【JVM深层系列】[HotSpotVM研究系列] JVM调优的"标准参数"的各种陷阱和坑点分析(攻克盲点及混淆点)「 1 」
- 【JVM故障问题排查心得】「内存诊断系列」Docker容器经常被kill掉,k8s中该节点的pod也被驱赶,怎么分析?
- 【深入浅出SpringCloud原理及实战】「SpringCloud-Alibaba系列」微服务模式搭建系统基础架构实战指南及版本规划踩坑分析
- 【秒杀购物商城业务服务】「分布式架构服务」盘点中间件服务的高可用模式及集群技术的方案分析
- 作者推荐 | 【分布式技术专题】「架构设计方案」图解学习法总结集群模式下的各种软负载均衡策略实现及原理分析
- 【分布式技术专题】「架构设计方案」盘点和总结秒杀服务的功能设计及注意事项技术体系
- Kafka技术专题之「性能调优篇」消息队列服务端出现内存溢出OOM以及相关性能调优实战分析
- 深入浅出学习透析Nginx服务器的基本原理和配置指南「初级实践篇 」
- 深入浅出学习透析 Nginx 服务器的基本原理和配置指南「运维操作实战篇」
- 【JVM故障问题排查心得】「内存诊断系列」JVM内存与Kubernetes中pod的内存、容器的内存不一致所引发的OOMKilled问题总结(下)
- 【JVM故障问题排查心得】「内存诊断系列」JVM内存与Kubernetes中pod的内存、容器的内存不一致所引发的OOMKilled问题总结(上)
- 深入浅出学习透析Nginx服务器的基本原理和配置指南「Keepalive性能分析实战篇」
- 🍃【Spring专题】「开发指南」手把手教你将@Schedule任务调度升级为分布式调度@DistributeSchedule
- Zookeeper的服务器的log4j升级为log4j2的升级方案(忽略配置化兼容问题)
- 🏆【Alibaba中间件技术系列】「RocketMQ技术专题」系统服务底层原理以及高性能存储设计分析
- 🏆【Alibaba中间件技术系列】「Nacos技术专题」服务注册与发现相关的原理分析