算法系列15天速成第四天五大經(jīng)典查找【上】

更新時間：2013年11月10日 10:30:26 作者：

在我們的生活中，無處不存在著查找，比如找一下班里哪個mm最pl，猜一猜mm的芳齡....... 對的這些都是查找

在我們的算法中，有一種叫做線性查找。

分為：順序查找。
折半查找。

查找有兩種形態(tài)：

分為：破壞性查找，比如有一群mm，我猜她們的年齡，第一位猜到了是23+，此時這位mm已經(jīng)從我腦海里面的mmlist中remove掉了。

哥不找23+的，所以此種查找破壞了原來的結(jié)構(gòu)。

非破壞性查找，這種就反之了，不破壞結(jié)構(gòu)。

順序查找：

這種非常簡單，就是過一下數(shù)組，一個一個的比，找到為止。

復(fù)制代碼代碼如下:

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 已經(jīng)在數(shù)組中找到，索引位置為：" + 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;
        }
    }
}

折半查找: 這種查找很有意思，就是每次都砍掉一半，

比如"幸運52“中的猜價格游戲，價格在999元以下，1分鐘之內(nèi)能猜到幾樣給幾樣，如果那些選手都知道折半查找，
那結(jié)果是相當(dāng)?shù)陌　?/P>

不過要注意，這種查找有兩個缺點：

第一：數(shù)組必須有序，不是有序就必須讓其有序，大家也知道最快的排序也是NLogN的，所以.....嗚嗚。
第二：這種查找只限于線性的順序存儲結(jié)構(gòu)。

上代碼:

復(fù)制代碼代碼如下:

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 已經(jīng)在數(shù)組中找到，索引位置為：" + 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;
        }
    }
}