分治算法二分搜索技術(shù)

1、分治算法(一)二分搜索技術(shù)分治算法的本質(zhì)就是將一個(gè)大規(guī)模的問(wèn)題分解為若干個(gè)小規(guī)模的相同子問(wèn)題，分而治之。分治算法簡(jiǎn)述1.1分治算法也有它的適用條件，滿足以下3個(gè)條件，才能使用分治法來(lái)解決：原問(wèn)題可分解為若干個(gè)規(guī)模較小的相同子問(wèn)題子問(wèn)題相互獨(dú)立子問(wèn)題的解可以合并為原問(wèn)題的解1.2使用分治法解題的步驟：分解：將要解決的問(wèn)題分解為若干個(gè)規(guī)模較小、相互獨(dú)立、與原問(wèn)題形式相同的子問(wèn)題。治理：對(duì)子問(wèn)題進(jìn)行求解。合并：按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。用二分搜索技術(shù)玩猜數(shù)字游戲2.1問(wèn)題描述假如你女朋友想跟你玩一個(gè)游戲，說(shuō)：“親愛(ài)的，猜一下我心里想的是哪個(gè)數(shù)字？這個(gè)數(shù)字在110范圍內(nèi)。”你

2、可能會(huì)猜1,女朋友說(shuō)：“小了?！苯又悴?,女朋友說(shuō)：“小了?！苯又阌植?,女朋友還是說(shuō)：“小了?！边@時(shí)候女朋友會(huì)很無(wú)奈地說(shuō)：“天吶，你怎么可以這么笨！”這樣每次加1的方法來(lái)猜，如果給定的數(shù)字是1,那么很幸運(yùn)，一次就能猜中；但是如果給定的是10,用這種方法就需要猜10次。推廣開來(lái)，如果是n個(gè)數(shù)，使用這種方法最壞的情況要猜n次才能成功。如何能夠用最少次數(shù)猜中給定的數(shù)字？我們的二分查找(也叫折半查找)可以很好地解決這個(gè)問(wèn)題。就拿上面問(wèn)題為例，因?yàn)檫@些數(shù)字(1到10)是有序(升序)的，使用二分查找每次和中間元素比較，如果提示說(shuō)猜的數(shù)字比給定的數(shù)字小了，即給定數(shù)字比中間元素大，則在后半部分查找；如果

3、提示說(shuō)猜的數(shù)字比給定的數(shù)字大了，即給定數(shù)字比中間元素小,則在前半部分查找。這樣每次查找,問(wèn)題都會(huì)縮小為上次問(wèn)題規(guī)模的一半,所以也被稱為折半查找。2.2算法設(shè)計(jì)用列表num存儲(chǔ)該有序序列(假定為升序)，設(shè)變量low表示查找范圍的下界，high表示查找范圍的上界，middle表示查找范圍的中間位置，x為特定的查找元素。初始化。令low=0,即指向有序列表num的第一個(gè)元素(列表元素下標(biāo)從0開始)；high=n-1,即指向有序列表num的最后一個(gè)元素,n表示列表長(zhǎng)度，也就是列表元素的個(gè)數(shù)。middle=(low+high)/2,即指向查找范圍的中間元素(low+high)為奇數(shù)的話，除以2并不能得到

4、整數(shù)，但是列表中元素的下標(biāo)都是整數(shù),這里實(shí)際上是向下取整,比如：3.5向下取整為3。判定lownummiddle,令low=middle+1;如果xnummiddle,令high=middle-1,轉(zhuǎn)為第2步。2.3算法實(shí)現(xiàn)(1)非遞歸實(shí)現(xiàn)numList=#定義一個(gè)計(jì)數(shù)變量，統(tǒng)計(jì)查找次數(shù)count=1defBinarySearch(numList,x):low=0high=len(numList)-1globalcountwhile(low=high):#地板除向下取整middle=(low+high)/2ifx=numListmiddle:#指定元素等于中間元素，查找成功，返回元素下標(biāo)returnmiddleelifxhigh:returnNonemiddle=(low+high)/2ifx=numListmiddle:returnmiddleelifxnumListmiddle:returnrecusionBS(numList,x,low,middle-1)else:returnrecusionBS(numList,x,middle+1