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