5.4.2二分查找課件-浙教版高中信息技術(shù)選修1

5.4.2二分查找猜數(shù)游戲假設(shè)在1-100以內(nèi)尋找某一個(gè)整數(shù)，如果我們每次都通過中間值來進(jìn)行查找某一個(gè)數(shù)，那么我們幾次以內(nèi)能找到這個(gè)數(shù)？24502513192223247次找到！如果要找的數(shù)是其它數(shù)呢？二分查找又稱折半查找，對(duì)分查找。它是一種效率很高的查找方法，但被查找的數(shù)據(jù)序列必須是有序的。二分查找首先將查找鍵與有序數(shù)組內(nèi)處于中間位置的元素進(jìn)行比較，如果中間位置上的元素的數(shù)值與查找鍵不同，根據(jù)數(shù)組元素的有序性，就可確定在數(shù)組的前半部分還是后半部分繼續(xù)查找；在新確定的范圍內(nèi)，繼續(xù)按上述方法進(jìn)行查找，直到獲得最終結(jié)果。在數(shù)組中的數(shù)據(jù)是有序的，若是升序的，是指下標(biāo)越小的數(shù)組元素中存儲(chǔ)的數(shù)據(jù)也越小，降序則相反。為簡(jiǎn)單起見，設(shè)數(shù)組d中存儲(chǔ)了n個(gè)互不相同的數(shù)據(jù)，并且數(shù)組d中的數(shù)據(jù)是升序的，則應(yīng)有：d[0]<d[1]<…<d[n-2]<d[n-1]。使用兩個(gè)變量i和j分別記錄查找范圍內(nèi)的第一個(gè)數(shù)組元素和最后一個(gè)數(shù)組元素的下標(biāo)。開始時(shí)，整個(gè)數(shù)組中的所有n個(gè)元素都在查找范圍內(nèi)，即變量i的初值為0，j的初值為n-1，用(i,j)表示查找范圍從d[i]起到d[j]為止。二分查找的基本方法是：在查找范圍（i,j）內(nèi)，可以利用數(shù)據(jù)的有序性，而不必逐個(gè)地進(jìn)行查找。

（a）key<d[m]，查找鍵小于中點(diǎn)d[m]處的數(shù)據(jù)。因?yàn)閿?shù)組d中的數(shù)據(jù)遞增，可以確定在（m,j）內(nèi)不可能存在值為key的數(shù)據(jù)，所以只需在新的范圍（i,m-1）中繼續(xù)查找。（b）key=d[m]，找到了需要的數(shù)據(jù)。（c）key>d[m]，由與（a）相同的理由，只需在新的范圍（m+1,j）中繼續(xù)查找。在通過一次比較后，新的查找范圍不會(huì)超過上一次查找范圍的一半。以規(guī)模為11的數(shù)組d為例，觀察二分查找的過程。在數(shù)組d的11個(gè)元素中，已按增序存儲(chǔ)了11個(gè)數(shù)據(jù)，要尋找的數(shù)據(jù)為12（已存儲(chǔ)在變量key中）。查找過程中，查找范圍的變化情況如下圖所示：612151822252835465860012345678910Key=12開始：ij第一次比較：612151822252835465860012345678910ijm第二次比較：612151822252835465860012345678910ijm第三次比較：612151822252835465860012345678910ijm第四次比較：612151822252835465860012345678910ijm查找成功！規(guī)模為n的數(shù)組中進(jìn)行二分查找的流程圖。開始i0,jn-1i≤j?是計(jì)算中點(diǎn)m[(i+j)/2]d[m]=key?找到，輸出信息是否否未找到，輸出信息結(jié)束key<d[m]?jm-1im+1是否實(shí)現(xiàn)此算法的Python程序：key=12d=[6,12,15,18,22,25,28,35,46,58,60]f=False#i和j定義子數(shù)組的邊界，一開始搜索的是整個(gè)數(shù)組i=0j=len(d)-1whilei<=j:m=(i+j)//2ifd[m]==key:f=Trueb=mbreakifkey<d[m]:#到左邊去找j=m-1else:#到右邊去找i=m+1iff==True:print(“查找成功！第”+str(b)+”個(gè)”)else:print(“沒有找到！”)另一種寫法：d=[6,12,15,18,22,25,28,35,46,58,60]i=0j=len(d)-1key=int(input(‘請(qǐng)輸入查找值：’))whilei<=j:m=(i+j)//2ifd[m]==key:print(“找到了，索引位置為：”,m)breakifkey<d[m]:#到左邊去找j=m-1else:#到右邊去找i=m+1ifi>j:print(“沒有找到！”)二分查找過程中，在每次關(guān)鍵字比較時(shí)，如果不匹配，那么根據(jù)匹配結(jié)果將查找表一分為二，排除沒有包含查找鍵的那一半，然后在可能含有查找鍵的那一半中繼續(xù)二分查找，直至找到查找鍵或找遍整個(gè)數(shù)組。處理思想是將一個(gè)大范圍的查找問題轉(zhuǎn)化為一個(gè)與原問題相似的查找范圍較小的查找問題，并且查找能在一定條件下停止。這個(gè)思想符合遞歸算法的思想。二分查找算法的遞歸實(shí)現(xiàn)defbsearch(s,array):iflen(array)==0:print(“未找到！”)returnFalsemid=(len(array)-1)//2ifarray[mid]==s:print(“找到了!”)returnTrueelifs<array[mid]:returnbsearch(s,array[:mid])else:returnbsearch(s,array[mid+1:])key=12d=[6,12,15,18,22,25,28,35,46,58,60]print(bsearch(key,d))若查找對(duì)象采用鏈表結(jié)構(gòu)，能否適用二分查找？一般而言，鏈表結(jié)構(gòu)不適合采用二分查找，但這又并非絕對(duì)，鏈表結(jié)構(gòu)可以通過數(shù)組來實(shí)現(xiàn)，從而二分查找也適用。二分查找過程可用一棵二叉樹來描述，樹中的每個(gè)根節(jié)點(diǎn)對(duì)應(yīng)當(dāng)前查找區(qū)間的中點(diǎn)元素，它的左子樹和右子樹分別對(duì)應(yīng)該區(qū)間的左子表和右子表，如下圖所示：251561218224628355860二分查找的判定樹實(shí)例查找key為12的元素比較次數(shù)為4次

由于二分查找在有序表上進(jìn)行，所以其對(duì)應(yīng)的判定樹就是一棵二叉排序樹。二叉排序樹也稱為二叉查找樹，這種結(jié)構(gòu)的二叉樹既能實(shí)現(xiàn)排序功能，也能實(shí)現(xiàn)查找功能。一、排序二叉排序樹的排序功能主要通過二叉樹的建立和遍歷過程來實(shí)現(xiàn)，其在建立過程中要始終滿足如下性質(zhì)：1.若它的左子樹不為空，則左子樹上的所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值。2.若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。3.它的左右子樹也分別為二叉排序樹。一組數(shù)據(jù)“23,20,13,18,14,11”建立的二叉排序樹如下圖所示，對(duì)此二叉樹進(jìn)行中序遍歷時(shí)，結(jié)果為從小到大的有序序列：23201311181411,13,14,18,20,23二、查找二叉查找樹的查找過程為：首先將給定值和根節(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功；若不相等，則根據(jù)給定值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，在左子樹或右子樹中繼續(xù)進(jìn)行查找。若查到為空樹時(shí)，說明該樹中沒有待查記錄，故查找不成功。232013111814查找關(guān)鍵字key為14的節(jié)點(diǎn)小小大小路徑：2320131814

練一練：1.在有序數(shù)組[12,23,34,45,46,5