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

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

分为：顺序查找。
折半查找。

查找有两种形态：

分为：破坏性查找， 比如有一群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();
}

///