算法系列15天速成 第四天 五大经典查找【上】
算法系列15天速成 第四天 五大经典查找【上】
发布时间:2016-12-29 来源:查字典编辑
摘要:在我们的算法中,有一种叫做线性查找。分为:顺序查找。折半查找。查找有两种形态:分为:破坏性查找,比如有一群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<int> list = new List<int>() { 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<int> list, int key)

{

for (int i = 0; i < list.Count; i++)

{

//查找成功,返回序列号

if (key == list[i])

return i;

}

//未能查找,返回-1

return -1;

}

}

}

算法系列15天速成 第四天 五大经典查找【上】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<int> list = new List<int>() { 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();

}

///<summary>

/// 折半查找

///</summary>

///<param name="list"></param>

///<returns></returns>

public static int BinarySearch(List<int> 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;

}

}

}

算法系列15天速成 第四天 五大经典查找【上】2

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

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

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

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

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

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

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新相关技巧学习
热门相关技巧学习
编程开发子分类