常用的查找算法

1. 順序查找
2. 二分法查找
3. 分塊查找
4. 散列表查找（哈希表）

順序查找的基本思想：

從表的一端開始，順序掃描表，依次將掃描到的結(jié)點關(guān)鍵字和給定值（假定為a）相比較，若當前結(jié)點關(guān)鍵字與a相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于a的結(jié)點，則查找失敗。

說白了就是，從頭到尾，一個一個地比，找著相同的就成功，找不到就失敗。很明顯的缺點就是查找效率低。

適用于線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。

計算平均查找長度。

例如上表，查找1，需要1次，查找2需要2次，依次往下推，可知查找16需要16次，

可以看出，我們只要將這些查找次數(shù)求和（我們初中學的，上底加下底乘以高除以2），然后除以結(jié)點數(shù)，即為平均查找長度。

設(shè)n=節(jié)點數(shù)

平均查找長度=（n+1）/2

演示代碼：

int[] aa = { 3, 6, 8, 7, 10, 15, 12, 14, 16, 17, 20, 21 };for (int i = 0; i < aa.Length; i++){  if(8 == aa[i])  {   Console.WriteLine("找到目標元素");  }}

二分法查找（折半查找）的基本思想：

（1）確定該區(qū)間的中點位置：mid=（low+high）/2

min代表區(qū)間中間的結(jié)點的位置，low代表區(qū)間最左結(jié)點位置，high代表區(qū)間最右結(jié)點位置

（2）將待查a值與結(jié)點mid的關(guān)鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則確定新的查找區(qū)間：

如果R[mid].key>a，則由表的有序性可知，R[mid].key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在R[mid].key左邊的表中。這時high=mid-1

如果R[mid].key<a,則等于a的關(guān)鍵字如果存在，必然在R[mid].key右邊的表中。這時low=mid

如果R[mid].key=a，則查找成功。

（3）下一次查找針對新的查找區(qū)間，重復(fù)步驟（1）和（2）

（4）在查找過程中，low逐步增加，high逐步減少，如果high<low，則查找失敗。

平均查找長度=Log2(n+1)-1

注：雖然二分法查找的效率高，但是要將表按關(guān)鍵字排序。而排序本身是一種很費時的運算，所以二分法比較適用于順序存儲結(jié)構(gòu)。為保持表的有序性，在順序結(jié)構(gòu)中插入和刪除都必須移動大量的結(jié)點。因此，二分查找特別適用于那種一經(jīng)建立就很少改動而又經(jīng)常需要查找的線性表。

代碼實現(xiàn)：

       /// <summary>        /// 二分法查找        /// </summary>        /// <param name="array">目標數(shù)組(已經(jīng)排序好了)</param>        /// <param name="a">查找的數(shù)</param>        /// <returns>目標數(shù)的索引</returns>        public int BinarySearch(int[] array, int T)        {            int low, high, mid;            low = 0;            high = array.Length - 1;            while (low <= high)            {                mid = (low + high) / 2;                if (array[mid] < T)                {                    low = mid + 1;                }                else if (array[mid]>T)                {                    high = mid - 1;                }                else                {                    return mid;                }            }            return -1;        }

分塊查找的基本思想：

分塊查找(Blocking Search)又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找方法

前提條件： 塊內(nèi)無序塊間有序方法：二分查找塊間 順序查找塊內(nèi)二分查找表由"分塊有序"的線性表和索引表組成1."分塊有序"的線性表表R[1..n]均分為b塊，前b-1塊中結(jié)點個數(shù)為 s ，第b塊的結(jié)點數(shù)小于等于s；每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即表是"分塊有序"的。2.索引表抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索引表ID[l..b]，即：ID[i](1≤i≤b)中存放第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個遞增有序表。因此采用順序或二分查找索引表，以確定待查結(jié)點在哪一塊，由于塊內(nèi)無序，只能用順序查找

using System;using System.Collections.Generic;using System.Text;namespace 分塊查找{    class PRogram    {        static void Main(string[] args)        {            int[] aa = { 3, 6, 8, 7, 10, 15, 12, 14, 16, 17, 20, 21 };            for (int i = 0; i < aa.Length; i++)            {                if (8 == aa[i])                {                    Console.WriteLine("找到目標元素");                }            }            int ysnum, zu, ww = 0;            for (int aa1 = 0; aa1 < aa.Length; aa1++)                Console.Write(aa[aa1] + " ");            Console.WriteLine();            Console.WriteLine("元素個數(shù)：{0}", aa.Length);            ysnum = aa.Length;            #region 分塊            Console.Write("請輸入組數(shù)：");            zu = Convert.ToInt32(Console.ReadLine());            int d = aa.Length / zu;            int[,] fenkuai = new int[zu, d];            Console.WriteLine("分塊如下：");            for (int z = 0; z < zu; z++)//進行分塊                for (int y = 0; y < d; y++)                {                    fenkuai[z, y] = aa[ww];                    ww++;                }            for (int z = 0; z < zu; z++)//輸出分塊            {                for (int y = 0; y < d; y++)                {                    Console.Write("{0}  ", fenkuai[z, y]);                }                Console.WriteLine();            }            #endregion            #region 確定各分塊的索引表            Console.WriteLine("關(guān)鍵字：");            int[] suoyin = new int[zu];            int q = 0;            int index = 0;            for (int z = 0; z < zu; z++)            {                int y;                for (y = 0; y < d; y++)                {                    if (q < fenkuai[z, y])                    {                        q = fenkuai[z, y];                    }                }                //Console.Write("{0}  ", q);//輸出索引表                ////建立索引表                if (index < zu)                {                    suoyin[index] = q;                }                index++;            }            for (int n = 0; n < zu; n++)            {                Console.Write(suoyin[n] + " ");            }            #endregion            #region 塊內(nèi)進行順序查找            Console.WriteLine("請輸入要查找的值：");            int kk = Convert.ToInt32(Console.ReadLine());            int pp = shunxu(suoyin, kk);            for (int n = 0; n < d; n++)            {                if (kk == fenkuai[pp, n])                {                    Console.WriteLine("該數(shù)值在元素當中");                }            }            #endregion            Console.ReadLine();        }        public static int shunxu(int[] aa, int k)        {            for (int a = 0; a < aa.Length - 1; a++)            {                if (k <= aa[a])                {                    return a;                }            }            return -1;        }    }}

散列表查找（哈希表）

哈希技術(shù)是查找和檢索與唯一標識鍵相關(guān)信息的最好方法之一。哈希表的基本原理是將給定的鍵值轉(zhuǎn)換為偏移地址來檢索記錄。

鍵轉(zhuǎn)換為地址是通過一種關(guān)系來完成，就是哈希函數(shù)。哈希函數(shù)對鍵執(zhí)行操作，從而給定一個哈希值，該值是代表可以找到該記錄的位置。

哈希法的基本思想是：設(shè)置一個長度為m的表T，用一個函數(shù)將數(shù)據(jù)集合中n個記錄的關(guān)鍵字盡可能唯一地轉(zhuǎn)換成0~m-1范圍內(nèi)的數(shù)值

哈希表的沖突現(xiàn)象

兩個不同的關(guān)鍵字，由于哈希函數(shù)值相同，因而被映射到同一個位置，為沖突。

解決哈希沖突

鏈表法：將所有關(guān)鍵字為同義詞的結(jié)點鏈接在同一個單鏈表中。即同一位置用單鏈表存儲鍵相同而值不同的記錄。

   /// <summary>        /// 在哈希表中插入記錄，用鏈表法解決沖突        /// </summary>        /// <param name="a"></param>        /// <param name="key"></param>        /// <param name="Mod"></param>        /// <returns></returns>        public bool HashInsert(chaintype[] a, int key, int Mod)        {            int i;            i = Hash(key, Mod);            chaintype pre;            chaintype cur;            pre = a[i];            cur = a[i];            while (cur != null && cur.Key != key)            {                pre = cur;                cur = cur.Next;            }            /*未查找到時插入該記錄在對應(yīng)的鏈表尾*/            if (cur == null)            {                cur = new chaintype();                cur.Key = key;                cur.Next = null;                /*在該鏈插入第一個記錄*/                if (a[i] == null)                    a[i] = cur;                else                    pre.Next = cur;                return true;            }            return false;        }        public chaintype HashSearch(chaintype[] a, int key, int Mod)        {            chaintype p;            int i = Hash(key, Mod);            p = a[i];            while (p != null && p.Key != key)            { p = p.Next; }            if (p == null) return null;            else                return p;        }

代碼調(diào)用：

      searchA.H