查找是在大量的信息中尋找一個(gè)特定的信息元素，在計(jì)算機(jī)應(yīng)用中，查找是常用的基本運(yùn)算，例如編譯程序中符號(hào)表的查找。本文簡(jiǎn)單概括性的介紹了常見的七種查找算法，說是七種，其實(shí)二分查找、插值查找以及斐波那契查找都可以歸為一類——插值查找。插值查找和斐波那契查找是在二分查找的基礎(chǔ)上的優(yōu)化查找算法。樹表查找和哈希查找會(huì)在后續(xù)的博文中進(jìn)行詳細(xì)介紹。

查找定義：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。

查找算法分類：
　　1）靜態(tài)查找和動(dòng)態(tài)查找；
　　　　注：靜態(tài)或者動(dòng)態(tài)都是針對(duì)查找表而言的。動(dòng)態(tài)表指查找表中有刪除和插入操作的表。
　　2）無(wú)序查找和有序查找。
　　　　無(wú)序查找：被查找數(shù)列有序無(wú)序均可；
　　　　有序查找：被查找數(shù)列必須為有序數(shù)列。

平均查找長(zhǎng)度（Average Search Length，ASL）：需和指定key進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。

對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為：ASL = Pi*Ci的和。
　　Pi：查找表中第i個(gè)數(shù)據(jù)元素的概率。
　　Ci：找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過的次數(shù)。

1. 順序查找

說明：順序查找適合于存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)或鏈接存儲(chǔ)的線性表。

基本思想：順序查找也稱為線形查找，屬于無(wú)序查找算法。從數(shù)據(jù)結(jié)構(gòu)線形表的一端開始，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值k相比較，若相等則表示查找成功；若掃描結(jié)束仍沒有找到關(guān)鍵字等于k的結(jié)點(diǎn)，表示查找失敗。

復(fù)雜度分析：　
　　查找成功時(shí)的平均查找長(zhǎng)度為：（假設(shè)每個(gè)數(shù)據(jù)元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
　　當(dāng)查找不成功時(shí)，需要n+1次比較，時(shí)間復(fù)雜度為O(n);
　　所以，順序查找的時(shí)間復(fù)雜度為O(n)。

int Sequential_Search(int *a,int n,int key){
   for (int i = 1; i <= n ; i++)
       if (a[i] == key)
           return i;
  
   return 0;
}

2. 二分查找

說明：元素必須是有序的，如果是無(wú)序的則要先進(jìn)行排序操作。

基本思想：也稱為是折半查找，屬于有序查找算法。用給定值k先與中間結(jié)點(diǎn)的關(guān)鍵字比較，中間結(jié)點(diǎn)把線形表分成兩個(gè)子表，若相等則查找成功；若不相等，再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果確定下一步查找哪個(gè)子表，這樣遞歸進(jìn)行，直到查找到或查找結(jié)束發(fā)現(xiàn)表中沒有這樣的結(jié)點(diǎn)。

復(fù)雜度分析：最壞情況下，關(guān)鍵詞比較次數(shù)為log2(n+1)，且期望時(shí)間復(fù)雜度為O(log2n)；

注：折半查找的前提條件是需要有序表順序存儲(chǔ)，對(duì)于靜態(tài)查找表，一次排序后不再變化，折半查找能得到不錯(cuò)的效率。但對(duì)于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來(lái)說，維護(hù)有序的排序會(huì)帶來(lái)不小的工作量，那就不建議使用?！洞笤挃?shù)據(jù)結(jié)構(gòu)》

int Binary_Search(int *a,int n,int key){
   
   int low,high,mid;
   low = 1;
   high = n;
   while (low <= high) {
       
       mid = (low + high) /2;

       if (key < a[mid]) {
           high = mid-1;
       }else if(key > a[mid]){
           low = mid+1;
       }else
           return mid;
   }
   
   return 0;
}

3. 插值查找

在介紹插值查找之前，首先考慮一個(gè)新問題，為什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

打個(gè)比方，在英文字典里面查“apple”，你下意識(shí)翻開字典是翻前面的書頁(yè)還是后面的書頁(yè)呢？如果再讓你查“zoo”，你又怎么查？很顯然，這里你絕對(duì)不會(huì)是從中間開始查起，而是有一定目的的往前或往后翻。
同樣的，比如要在取值范圍1 ~ 10000 之間 100 個(gè)元素從小到大均勻分布的數(shù)組中查找5， 我們自然會(huì)考慮從數(shù)組下標(biāo)較小的開始查找。
　　經(jīng)過以上分析，折半查找這種查找方式，不是自適應(yīng)的（也就是說是傻瓜式的）。二分查找中查找點(diǎn)計(jì)算如下：
　　mid=(low+high)/2, 即mid=low+1/2(high-low);
　　通過類比，我們可以將查找的點(diǎn)改進(jìn)為如下：
　　mid=low+(key-a[low])/(a[high]-a[low])(high-low)，
　　也就是將上述的比例參數(shù)1/2改進(jìn)為自適應(yīng)的，根據(jù)關(guān)鍵字在整個(gè)有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了比較次數(shù)。

基本思想：基于二分查找算法，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，可以提高查找效率。當(dāng)然，差值查找也屬于有序查找。

注：對(duì)于表長(zhǎng)較大，而關(guān)鍵字分布又比較均勻的查找表來(lái)說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。

復(fù)雜度分析：查找成功或者失敗的時(shí)間復(fù)雜度均為O(log2(log2n))。

int Interpolation_Search(int *a,int n,int key){
   int low,high,mid;
   low = 1;
   high = n;
   
   while (low <= high) {
       
       mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
   
       if (key < a[mid]) {
           high = mid-1;
       }else if(key > a[mid]){
           low = mid+1;
       }else
           return mid;
   }
   
   return 0;
}

4. 斐波那契查找

在介紹斐波那契查找算法之前，我們先介紹一下很它緊密相連并且大家都熟知的一個(gè)概念——黃金分割。

黃金比例又稱黃金分割，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。

0.618被公認(rèn)為最具有審美意義的比例數(shù)字，這個(gè)數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫、雕塑、音樂、建筑等藝術(shù)領(lǐng)域，而且在管理、工程設(shè)計(jì)等方面也有著不可忽視的作用。因此被稱為黃金分割。

大家記不記得斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（從第三個(gè)數(shù)開始，后邊每一個(gè)數(shù)都是前兩個(gè)數(shù)的和）。然后我們會(huì)發(fā)現(xiàn)，隨著斐波那契數(shù)列的遞增，前后兩個(gè)數(shù)的比值會(huì)越來(lái)越接近0.618，利用這個(gè)特性，我們就可以將黃金比例運(yùn)用到查找技術(shù)中。

基本思想：也是二分查找的一種提升算法，通過運(yùn)用黃金比例的概念在數(shù)列中選擇查找點(diǎn)進(jìn)行查找，提高查找效率。同樣地，斐波那契查找也屬于一種有序查找算法。
　　相對(duì)于折半查找，一般將待比較的key值與第mid=（low+high）/2位置的元素比較，比較結(jié)果分三種情況：
1）相等，mid位置的元素即為所求
2）大于，low=mid+1;
3）小于，high=mid-1。

斐波那契查找與折半查找很相似，他是根據(jù)斐波那契序列的特點(diǎn)對(duì)有序表進(jìn)行分割的。他要求開始表中記錄的個(gè)數(shù)為某個(gè)斐波那契數(shù)小1，及n=F(k)-1;

開始將k值與第F(k-1)位置的記錄進(jìn)行比較(及mid=low+F(k-1)-1),比較結(jié)果也分為三種
1）相等，mid位置的元素即為所求
2）大于，low=mid+1,k-=2;

說明：low=mid+1說明待查找的元素在[mid+1,high]范圍內(nèi)，k-=2 說明范圍[mid+1,high]內(nèi)的元素個(gè)數(shù)為n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個(gè)，所以可以遞歸的應(yīng)用斐波那契查找。

3）<，high=mid-1,k-=1。

說明：low=mid+1說明待查找的元素在[low,mid-1]范圍內(nèi)，k-=1 說明范圍[low,mid-1]內(nèi)的元素個(gè)數(shù)為F(k-1)-1個(gè)，所以可以遞歸 的應(yīng)用斐波那契查找。

復(fù)雜度分析：最壞情況下，時(shí)間復(fù)雜度為O(log2n)，且其期望復(fù)雜度也為O(log2n)。

int Fibonacci_Search(int *a,int n,int key){
 
   int low,high,mid,i,k;
   low = 1;
   high = n;
   k = 0;
   
   while (n > F[k]-1) {
       k++;
   }
   
   for(i = n;i < F[k]-1;i++)
       a[i] = a[n];
   
   while (low <= high) {
       
       mid = low+F[k-1]-1;
       
       if (key < a[mid]) {
           high = mid-1;
           k = k-1;
       }else if(key > a[mid]){
           low = mid+1;
           k = k-2;
           
       }else{
           if (mid <= n) {
               return mid;
           }else
           {
               return n;
           }
       }
   }
   return 0;
}

5. 最簡(jiǎn)單的樹表查找算法——二叉樹查找算法

基本思想：二叉查找樹是先對(duì)待查找的數(shù)據(jù)進(jìn)行生成樹，確保樹的左分支的值小于右分支的值，然后在就行和每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)比較大小，查找最適合的范圍。 這個(gè)算法的查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹。

二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
1）若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2）若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
3）任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

二叉查找樹性質(zhì)：對(duì)二叉查找樹進(jìn)行中序遍歷，即可得到有序的數(shù)列。

復(fù)雜度分析：它和二分查找一樣，插入和查找的時(shí)間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會(huì)有O(n)的時(shí)間復(fù)雜度。原因在于插入和刪除元素的時(shí)候，樹沒有保持平衡（比如，我們查找上圖（b）中的“93”，我們需要進(jìn)行n次查找操作）。我們追求的是在最壞的情況下仍然有較好的時(shí)間復(fù)雜度，這就是平衡查找樹設(shè)計(jì)的初衷。

基于二叉查找樹進(jìn)行優(yōu)化，進(jìn)而可以得到其他的樹表查找算法，如平衡樹、紅黑樹等高效算法。

二叉排序樹的查找、插入、刪除等操作

//二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義
//結(jié)點(diǎn)結(jié)構(gòu)
typedef  struct BiTNode
{
   //結(jié)點(diǎn)數(shù)據(jù)
   int data;
   //左右孩子指針
   struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//1.二叉排序樹--查找
/*
遞歸查找二叉排序樹T中,是否存在key;
指針f指向T的雙親,器初始值為NULL;
若查找成功,則指針p指向該數(shù)據(jù)元素的結(jié)點(diǎn),并且返回TRUE;
若指針p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)則返回FALSE;
*/
Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){
  
   if (!T)    /*  查找不成功 */
   {
       *p = f;
       return FALSE;
   }
   else if (key==T->data) /*  查找成功 */
   {
       *p = T;
       return TRUE;
   }
   else if (key<T->data)
       return SearchBST(T->lchild, key, T, p);  /*  在左子樹中繼續(xù)查找 */
   else
       return SearchBST(T->rchild, key, T, p);  /*  在右子樹中繼續(xù)查找 */
}

//2.二叉排序樹-插入
/*  當(dāng)二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)， */
/*  插入key并返回TRUE，否則返回FALSE */
Status InsertBST(BiTree *T, int key) {
   
   BiTree p,s;
   //1.查找插入的值是否存在二叉樹中;查找失敗則->
   if (!SearchBST(*T, key, NULL, &p)) {
       
       //2.初始化結(jié)點(diǎn)s,并將key賦值給s,將s的左右孩子結(jié)點(diǎn)暫時(shí)設(shè)置為NULL
       s = (BiTree)malloc(sizeof(BiTNode));
       s->data = key;
       s->lchild = s->rchild = NULL;
       
       //3.
       if (!p) {
           //如果p為空,則將s作為二叉樹新的根結(jié)點(diǎn);
           *T = s;
       }else if(key < p->data){
           //如果key<p->data,則將s插入為左孩子;
           p->lchild = s;
       }else
           //如果key>p->data,則將s插入為右孩子;
           p->rchild = s;
       
       return  TRUE;
   }
   
   return FALSE;
}

//3.從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或者右子樹;
Status Delete(BiTree *p){
   
   BiTree temp,s;
   
   
   if((*p)->rchild == NULL){
      
       //情況1: 如果當(dāng)前刪除的結(jié)點(diǎn),右子樹為空.那么則只需要重新連接它的左子樹;
       //①將結(jié)點(diǎn)p臨時(shí)存儲(chǔ)到temp中;
       temp = *p;
       //②將p指向到p的左子樹上;
       *p = (*p)->lchild;
       //③釋放需要?jiǎng)h除的temp結(jié)點(diǎn);
       free(temp);
       
   }else if((*p)->lchild == NULL){
       
       //情況2:如果當(dāng)前刪除的結(jié)點(diǎn),左子樹為空.那么則只需要重新連接它的右子樹;
       //①將結(jié)點(diǎn)p存儲(chǔ)到temp中;
       temp = *p;
       //②將p指向到p的右子樹上;
       *p = (*p)->rchild;
       //③釋放需要?jiǎng)h除的temp結(jié)點(diǎn)
       free(temp);
   }else{
       
       //情況③:刪除的當(dāng)前結(jié)點(diǎn)的左右子樹均不為空;
      
       //①將結(jié)點(diǎn)p存儲(chǔ)到臨時(shí)變量temp, 并且讓結(jié)點(diǎn)s指向p的左子樹
       temp = *p;
       s = (*p)->lchild;
     
       //②將s指針,向右到盡頭(目的是找到待刪結(jié)點(diǎn)的前驅(qū))
       //-在待刪除的結(jié)點(diǎn)的左子樹中,從右邊找到直接前驅(qū)
       //-使用`temp`保存好直接前驅(qū)的雙親結(jié)點(diǎn)
       while (s->rchild) {
           temp = s;
           s = s->rchild;
       }
       
       //③將要?jiǎng)h除的結(jié)點(diǎn)p數(shù)據(jù)賦值成s->data;
       (*p)->data = s->data;
       
       //④重連子樹
       //-如果temp 不等于p,則將S->lchild 賦值給temp->rchild
       //-如果temp 等于p,則將S->lchild 賦值給temp->lchild
       if(temp != *p)
           temp->rchild = s->lchild;
       else
           temp->lchild = s->lchild;
       
       //⑤刪除s指向的結(jié)點(diǎn); free(s)
       free(s);
   }
   
   return  TRUE;
}

//4.查找結(jié)點(diǎn),并將其在二叉排序中刪除;
/* 若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn), */
/* 并返回TRUE；否則返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{
   //不存在關(guān)鍵字等于key的數(shù)據(jù)元素
   if(!*T)
       return FALSE;
   else
   {
       //找到關(guān)鍵字等于key的數(shù)據(jù)元素
       if (key==(*T)->data)
           return Delete(T);
       else if (key<(*T)->data)
           //關(guān)鍵字key小于當(dāng)前結(jié)點(diǎn),則縮小查找范圍到它的左子樹;
           return DeleteBST(&(*T)->lchild,key);
       else
           //關(guān)鍵字key大于當(dāng)前結(jié)點(diǎn),則縮小查找范圍到它的右子樹;
           return DeleteBST(&(*T)->rchild,key);
       
   }
}