# 第四天 五大经典查找【上】

``` 1 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("呜呜，没有找到！");

}

//顺序查找
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;
}
}
}```

``` 1 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("呜呜，没有找到！");

}

///<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;
}
}
}```

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