折半查找，也稱二分查找，在某些情況下相比于順序查找，使用折半查找算法的效率更高。但是該算法的使用的前提是靜態(tài)查找表中的數(shù)據(jù)必須是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}這個(gè)查找表使用折半查找算法查找數(shù)據(jù)之前，需要首先對(duì)該表中的數(shù)據(jù)按照所查的關(guān)鍵字進(jìn)行排序：{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前對(duì)查找表按照所查的關(guān)鍵字進(jìn)行排序的意思是：若查找表中存儲(chǔ)的數(shù)據(jù)元素含有多個(gè)關(guān)鍵字時(shí)，使用哪種關(guān)鍵字做折半查找，就需要提前以該關(guān)鍵字對(duì)所有數(shù)據(jù)進(jìn)行排序。

折半查找算法

對(duì)靜態(tài)查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找關(guān)鍵字為 21 的過(guò)程為：


圖 1 折半查找的過(guò)程（a）
如上圖 1 所示，指針 low 和 high 分別指向查找表的第一個(gè)關(guān)鍵字和最后一個(gè)關(guān)鍵字，指針 mid 指向處于 low 和 high 指針中間位置的關(guān)鍵字。在查找的過(guò)程中每次都同 mid 指向的關(guān)鍵字進(jìn)行比較，由于整個(gè)表中的數(shù)據(jù)是有序的，因此在比較之后就可以知道要查找的關(guān)鍵字的大致位置。

例如在查找關(guān)鍵字 21 時(shí)，首先同 56 作比較，由于21 < 56，而且這個(gè)查找表是按照升序進(jìn)行排序的，所以可以判定如果靜態(tài)查找表中有 21 這個(gè)關(guān)鍵字，就一定存在于 low 和 mid 指向的區(qū)域中間。

因此，再次遍歷時(shí)需要更新 high 指針和 mid 指針的位置，令 high 指針移動(dòng)到 mid 指針的左側(cè)一個(gè)位置上，同時(shí)令 mid 重新指向 low 指針和 high 指針的中間位置。如圖 2 所示：


圖 2 折半查找的過(guò)程（b）
? 同樣，用 21 同 mid 指針指向的 19 作比較，19 < 21，所以可以判定 21 如果存在，肯定處于 mid 和 high 指向的區(qū)域中。所以令 low 指向 mid 右側(cè)一個(gè)位置上，同時(shí)更新 mid 的位置。



圖 3 折半查找的過(guò)程（3） 當(dāng)?shù)谌巫雠袛鄷r(shí)，發(fā)現(xiàn) mid 就是關(guān)鍵字 21 ，查找結(jié)束。

注意：在做查找的過(guò)程中，如果 low 指針和 high 指針的中間位置在計(jì)算時(shí)位于兩個(gè)關(guān)鍵字中間，即求得 mid 的位置不是整數(shù)，需要統(tǒng)一做取整操作。

折半查找的實(shí)現(xiàn)代碼： #include <stdio.h> #include <stdlib.h> #define keyType int
typedef struct
{keyType key;　　// 查找表中每個(gè)數(shù)據(jù)元素的值// 如果需要，還可以添加其他屬性 }ElemType;typedef struct
{ElemType *elem;　　// 存放查找表中數(shù)據(jù)元素的數(shù)組int length;　　　　 // 記錄查找表中數(shù)據(jù)的總數(shù)量 }SSTable;
// 創(chuàng)建查找表 void Create(SSTable **st, int length)
{(*st) = (SSTable*)malloc(sizeof(SSTable));(*st)->length = length;printf("輸入表中的數(shù)據(jù)元素：\n");// 根據(jù)查找表中數(shù)據(jù)元素的總長(zhǎng)度，在存儲(chǔ)時(shí)，從數(shù)組下標(biāo)為 1 的空間開始存儲(chǔ)數(shù)據(jù)for (int i=1; i<=length; i++)
　　 {scanf("%d", &((*st)->elem[i].key));} }
//折半查找算法 int Search_Bin(SSTable *ST, keyType key)
{int low = 1;　　//初始狀態(tài) low 指針指向第一個(gè)關(guān)鍵字int high = ST->length;　　//high 指向最后一個(gè)關(guān)鍵字int mid;while (low <= high)
　　{mid = (low+high) / 2;　　// int 本身為整形，所以，mid 每次為取整的整數(shù)if (ST->elem[mid].key == key)　　// 如果 mid 指向的同要查找的相等，返回 mid 所指向的位置 {return mid;}
　　　　 else if(ST->elem[mid].key > key)　　// 如果mid指向的關(guān)鍵字較大，則更新 high 指針的位置 {high = mid-1;}// 反之，則更新 low 指針的位置else
　　 {low = mid + 1;}}
return 0; }int main(int argc, const char * argv[])
{SSTable *st;Create(&st, 11);getchar();printf("請(qǐng)輸入查找數(shù)據(jù)的關(guān)鍵字：\n");int key;scanf("%d", &key);int location = Search_Bin(st, key);//如果返回值為 0，則證明查找表中未查到 key 值，if (location == 0)
　　 {printf("查找表中無(wú)該元素");}
　　 else
　　 {printf("數(shù)據(jù)在查找表中的位置為：%d", location);}return 0; }
以圖 1 的查找表為例，運(yùn)行結(jié)果為： 輸入表中的數(shù)據(jù)元素： 5 13 19 21 37 56 64 75 80 88 92 請(qǐng)輸入查找數(shù)據(jù)的關(guān)鍵字： 21 數(shù)據(jù)在查找表中的位置為：4

?

折半查找的性能分析

折半查找的運(yùn)行過(guò)程可以用二叉樹來(lái)描述，這棵樹通常稱為“判定樹”。例如圖 1 中的靜態(tài)查找表中做折半查找的過(guò)程，對(duì)應(yīng)的判定樹如圖 4：
圖 4 折半查找對(duì)應(yīng)的判定樹
在判定樹中可以看到，如果想在查找表中查找 21 的位置，只需要進(jìn)行 3 次比較，依次和 56、19、21 進(jìn)行比較，而比較的次數(shù)恰好是該關(guān)鍵字所在判定樹中的層次（關(guān)鍵字 21 在判定樹中的第 3 層）。

對(duì)于具有 n 個(gè)結(jié)點(diǎn)（查找表中含有 n 個(gè)關(guān)鍵字）的判定樹，它的層次數(shù)至多為：log₂n + 1（如果結(jié)果不是整數(shù)，則做取整操作，例如：?log₂11 +1 = 3 + 1 = 4?）。

同時(shí)，在查找表中各個(gè)關(guān)鍵字被查找概率相同的情況下，折半查找的平均查找長(zhǎng)度為：ASL = log₂(n+1) – 1。

總結(jié)

通過(guò)比較折半查找的平均查找長(zhǎng)度，同前面介紹的順序查找相對(duì)比，明顯折半查找的效率要高。但是折半查找算法只適用于有序表，同時(shí)僅限于查找表用順序存儲(chǔ)結(jié)構(gòu)表示。
當(dāng)查找表使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示時(shí)，折半查找算法無(wú)法有效地進(jìn)行比較操作（排序和查找操作的實(shí)現(xiàn)都異常繁瑣）。

轉(zhuǎn)載于:https://www.cnblogs.com/ciyeer/p/9065781.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的数据结构50：二分查找法(折半查找法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。