【正文】 167。 二分查找 （ Binary Search）又稱 折半查找 ，是一種效率較高的查找方法。二分查找要求順序表是有序表 167。 二分查找的 基本思想 是：初始時，查找區(qū)間為整個有序表，取查找區(qū)間的中間記錄作為比較對象，若中間記錄的關(guān)鍵字與給定值相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的前半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的后半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過程，直至新區(qū)間中間記錄的關(guān)鍵字等于給定值，則查找成功，或者查找區(qū)間不斷縮小直到為空，表明查找失敗。 167。 二分查找的具體查找步驟為： （ 1）設(shè)變量 low和 high表示查找區(qū)間的起始和終端下標(biāo)，初始時查找區(qū)間是 R[1]~R[N]， low取值為 1，high取值為 N。設(shè)變量 mid表示查找區(qū)間中間位置的下標(biāo)，計算公式： mid=? (low+hign)/2? （ 2）當(dāng) low≤high（查找區(qū)間非空）時，求 mid=? (low+hign)/2?，進(jìn)行如下比較： 若 k==R[mid].key，查找成功，返回記錄在表中位置 若 kR[mid].key，則 high=mid1，在前半?yún)^(qū)繼續(xù)查找 若 kR[mid].key，則 low=mid+1，在后半?yún)^(qū)繼續(xù)查找 （ 3）當(dāng) lowhigh時，查找區(qū)間為空，說明查找失敗 例 一個有序表中有 13個記錄，記錄的關(guān)鍵字序列為（ 7， 14， 18， 21， 23， 29， 31， 35， 38， 42， 46， 49， 52），給定值 k分別為 14和 22，在表中查找關(guān)鍵字與 k相等的記錄。 ↑ ↑ low=1 high=13 ↑ mid=7 ↑ ↑ low=1 high=6 kR[mid]，調(diào)整到前半?yún)^(qū)： high=mid1 ↑ mid=3 ↑ ↑ low=1 high=2 kR[mid]，調(diào)整到前半?yún)^(qū)： high=mid1 ↑ mid=1 ↑↑ low=high=2 kR[mid]，調(diào)整到后半?yún)^(qū)： low=mid+1 ↑ mid=2 k==R[mid]，查找成功，返回找到的記錄序號 2 查找 k=14的過程示意圖 7 14 18 21 23 29 31 35 38 42 46 49 52 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ↑ ↑ low=1 high=13 ↑ mid=7 ↑ ↑ low=1 high=6 kR[mid]， high=mid1 ↑ mid=3 ↑ ↑ low=4 high=6 kR[mid]， low=mid+1 ↑ mid=5 ↑↑ low=high=4 kR[mid]， high=mid1 ↑ mid=4 ↑ ↑ high=4 low=5 kR[mid]， low=mid+1 lowhigh 查找區(qū)間為空，查找失敗。 查找 k=22的過程示意圖 7 14 18 21 23 29 31 35 38 42 46 49 52 0 1 2 3 4 5 6 7 8 9 10 11 12 13 二分查找非遞歸算法的 C函數(shù)： int binarySearch(RecType R[ ], KeyType k) /*用二分查找法在數(shù)組 R中查找關(guān)鍵字為 k的記錄，若找到返回該記錄的位置，否則返回0。 */ { int low, hign, mid。 low=1。 high=N。 /*設(shè)置初始查找區(qū)間 */ while(low=high) /*查找區(qū)間非空 */ { mid=(low+high)/2。 /*計算查找區(qū)間中間位置的下標(biāo) */ if(k==R[mid].key) return mid。 /*查找成功，返回記錄的位置 */ else if(kR[mid].key) high=mid1。 /*調(diào)整到前半?yún)^(qū) */ else low=mid+1。 /*調(diào)整到后半?yún)^(qū) */ } return 0。 } 167。 二分查找過程 判定樹 例 查找成功情況下的平均查找長度為： ASL=（ 1+2 2+3 4+4 6） /13=36/13。 3 11 8 4 27 2 3 3 5 4 91 4 2 1 2 9 3 8 4 6 5 2查找不成功情況下的判定樹 查找不成功時的平均查找長度 ASL為： ASL不成功 =（ 3 2+4 12） /14=54/14。 3 11 84 27 2 3 3 54 91 4 2 1 2 9 3 8 4 6 5 2二分查找性能分析 167。 二分查找的平均查找長度 以樹高為 k的滿二叉樹為例，樹中共有 n=2k1個結(jié)點，第 i層有 2i1個結(jié)點，則二分查找的平均查找長度為： 167。 二分查找算法的平均時間復(fù)雜度為 O(log2n) 0 1 111 1 2 2 2 . . . 2n kiiiA S L P C kn ????? ? ? ? ? ? ? ????221 l o g ( 1 ) 1 l o g ( 1 ) 1n nnn?? ? ? ? ? ?167。 二分查找的特點 優(yōu)點：比較次數(shù)相對較少，查找效率較高。 缺點：在查找之前需要建立有序表，二分查找要求順序存儲有序表，因而在表中插入或刪除記錄都需要移動大量的記錄， 二分查找方法適合于數(shù)據(jù)相對穩(wěn)定的靜態(tài)查找表。 二分查找只適合順序存儲結(jié)構(gòu)，而不適合鏈接存儲結(jié)構(gòu)。 8． 3 索引查找 索引查找是建立在 索引存儲結(jié)構(gòu) 上的查找方法。 例如在英文字典里查找某個單詞的過程就是一個索引查找。把字典看作是索引查找的對象，其中，字典的正文是主要部分，稱作是 主表 ，字母索引表是為了方便查找而建立的索引，稱作是 索引表 。 8． 3． 1 索引表的組織 167。 索引存儲的 基本思想 是：除了存儲主表的記錄外，還要為主表建立一個或若干個附加的索引表。索引表用來標(biāo)識主表記錄的存儲位置，它由若干個被稱為 索引項 的數(shù)據(jù)元素組成。 167。 索引項的一般形式為 （索引關(guān)鍵字，地址），索引關(guān)鍵字是記錄的某個數(shù)據(jù)項，一般會是記錄的關(guān)鍵字，地址是用來標(biāo)識一個或一組記錄的存儲位置。 167。 若一個記錄對應(yīng)一個索引項，則該索引表為 稠密索引 （ Dense Index）。若一組記錄對應(yīng)一個索引項，則該索引表為 稀疏索引 （ Sparse Index）。 例 為表 。 編號 姓名 性別 職稱 電話號碼 所在院系 1001 劉林 女 講師 82626777 法學(xué)院 1002 趙紅 男 教授 67891234 法學(xué)院 1003 陳曲 女 副教授 68889245 法學(xué)院 1004 南方 男 講師 89891900 理學(xué)院 1005 朱紅 男 講師 23452345 理學(xué)院 1006 劉微微 女 副教授 56347812 外語學(xué)院 1007 陳俊亮 男 副教授 34512345 外語學(xué)院 1008 趙婷婷 女 講師 67645321 外語學(xué)院 1009 陳華 女 教授 89764567 藝術(shù)學(xué)院 1010 佟曉偉 男 講師 34523455 藝術(shù)學(xué)院 （ 1）稠密索引： 稠密索引為每個記錄建立索引項（索引關(guān)鍵字，地址） 主表： 0 1 2 3 4 5 6 7 8 9 … 索引表： 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 …… 關(guān)鍵字 地址 1001 0 1002 1 1003 2 1004 3 1005 4 1006 5 1007 6 1008 7 1009 8 1010 9 1） 稀疏索引：把主表的記錄按照某種規(guī)則劃分為幾個 子表 ，然后再為每個子表建立索引項（索引關(guān)鍵字，地址） 按照所在院系劃分，可以有 4個子表，分別為：法學(xué)院LA1=（ 1001， 1002， 1003），理學(xué)院 LA2=（ 1004，1005），外語學(xué)院 LA3=（ 1006， 1007， 1008），藝術(shù)學(xué)院 LA4=（ 1009，