博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法系列15天速成——第四天 五大经典查找【上】
阅读量:6073 次
发布时间:2019-06-20

本文共 2800 字,大约阅读时间需要 9 分钟。

在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都是查找。

 

在我们的算法中,有一种叫做线性查找。

分为:顺序查找。

        折半查找。

 

查找有两种形态:

分为:破坏性查找,   比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。

                            哥不找23+的,所以此种查找破坏了原来的结构。

       非破坏性查找, 这种就反之了,不破坏结构。 

 

顺序查找:

    这种非常简单,就是过一下数组,一个一个的比,找到为止。

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Sequential{    class Program    {        static void Main(string[] args)        {            List
list = new List
() { 2, 3, 5, 8, 7 }; var result = SequenceSearch(list, 3); if (result != -1) Console.WriteLine("3 已经在数组中找到,索引位置为:" + result); else Console.WriteLine("呜呜,没有找到!"); Console.Read(); } //顺序查找 static int SequenceSearch(List
list, int key) { for (int i = 0; i < list.Count; i++) { //查找成功,返回序列号 if (key == list[i]) return i; } //未能查找,返回-1 return -1; } }}

 

折半查找: 这种查找很有意思,就是每次都砍掉一半,

             比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,

             那结果是相当的啊。

           

不过要注意,这种查找有两个缺点:

            第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。

            第二: 这种查找只限于线性的顺序存储结构。

 

上代码:

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace BinarySearch{    class Program    {        static void Main(string[] args)        {            List
list = new List
() { 3, 7, 9, 10, 11, 24, 45, 66, 77 }; var result = BinarySearch(list, 45); if (result != -1) Console.WriteLine("45 已经在数组中找到,索引位置为:" + result); else Console.WriteLine("呜呜,没有找到!"); Console.Read(); } ///
/// 折半查找//////
///
public static int BinarySearch(List
list, int key) { //最低线 int low = 0; //最高线 int high = list.Count - 1; while (low <= high) { //取中间值 var middle = (low + high) / 2; if (list[middle] == key) { return middle; } else if (list[middle] > key) { //下降一半 high = middle - 1; } else { //上升一半 low = middle + 1; } } //未找到 return -1; } }}

  

     先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,

可能都导致数组元素的整体前移或后移。

    所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。

 

ps:  线性查找时间复杂度:O(n);

         折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);

         折半有序的时间复杂度:O(logN);

转载地址:http://rcsgx.baihongyu.com/

你可能感兴趣的文章
hdu 4965 矩阵快速幂 矩阵相乘性质
查看>>
iOS - App 应用
查看>>
用户登录验证
查看>>
TSVNCache.exe严重占用CPU问题
查看>>
详细易懂的解释变量和指针变量重新赋值的过程和问题
查看>>
Python 操作 MYSQL
查看>>
关于解决javaEE端口占用的方法
查看>>
mysql 更改表名称
查看>>
handlerbars入门学习
查看>>
关于“VS2010语法检查红线不见了”的解决方案
查看>>
C++模板使用介绍
查看>>
Object-C中 - self 和super 的含义
查看>>
Optimizing graphics performance
查看>>
C#方法拓展
查看>>
kafka的分区分配策略
查看>>
react-keeper
查看>>
react 项目实战(十)引入AntDesign组件库
查看>>
flexible.js + makegrid.js 自适应布局
查看>>
js 判断对象中所有属性是否为空
查看>>
Scrapy基础(六)————Scrapy爬取伯乐在线一通过css和xpath解析文章字段
查看>>