計算與人工智能概論第5章算法思維第二節(jié)二分法

二分法

1PART在一個線性序列（例如列表）中，查找指定的值，若找到，返回索引，這就是搜索。通常來說，直接從頭到尾進行搜索的算法是非常消耗時間的，時間復(fù)雜度為O(n)，n為序列的長度。搜索算法defsearch(A,x):fori,ainenumerate(A):ifx==a:returnireturn-1#沒找到返回-1A=[52,49,6,24,19,60,134,88]idx=search(A,19)print(index)實際上，list自帶搜索函數(shù)，其實現(xiàn)方式和左邊的代碼類似，時間復(fù)雜度都是O(n):A=[52,49,6,24,19,60,134,88]idx=A.index(19)#搜索函數(shù)print(idx)搜索算法使用二分法進行搜索是經(jīng)典的搜索算法，指的是在一個已經(jīng)排序的序列中，查找指定的值，若找到，返回索引。二分搜索可以極大的提高查找效率，其時間復(fù)雜度是O(logn)，當然，它要求序列是已經(jīng)排好序的。在40億個已排序數(shù)據(jù)中查找一個數(shù)時，二分搜索最多循環(huán)32次。232=4294967296≈40億二分搜索考慮我們怎么查字典？會不會從第一頁開始查？1翻到中間位置，如果該位置的首字母比要查的首字母大，我們知道要查的一定在該位置前面，此時，該位置后面的部分可以拋棄（假定撕掉這部分）；如果比要查的首字母小，則撕掉前面的部分。2在剩下的部分中，再翻到中間位置，再比較，按同樣的方法撕掉不需要的部分。3持續(xù)這個過程，直到翻到的位置恰好有要查的單詞或者只剩下一頁紙。以上方法就是二分法，人類在生活中經(jīng)常使用，二分法也是計算機的一個經(jīng)典算法。二分法的核心：每次都將解的搜索空間大小縮小為原先的一半。二分搜索二分查找的基本思想1在列表A的區(qū)間[i,j](i<=j)中查找x，其中i,j為索引。2考察區(qū)間中間的元素的值，y=A[(i+j)//2]，若x==y，算法結(jié)束；若x<y，則x必定位于原區(qū)間的左半邊即[i,(i+j)//2-1]；若x>y，則x必定位于原區(qū)間的右半邊，即[(i+j)//2+1,j]3在新的區(qū)間（原區(qū)間一半大?。┲欣^續(xù)查找。4重復(fù)2、3的步驟，區(qū)間不斷縮小直到找到5若直到區(qū)間無效時(i>j)，還沒找到x，則x不在A中。二分搜索defbinary_search(A,x):i,j=0,len(A)-1whilei<=j:k=(i+j)//2ifx==A[k]:returnkelifx<A[k]:j=k-1else:i=k+1return-1#沒找到返回-1A=[2,4,6,14,19,20,34,88]index=binary_search(A,21)print(index)時間復(fù)雜度為O(logn)在40億個已排序數(shù)據(jù)中查找一個數(shù)最多循環(huán)32次。232=4294967296≈40億二分搜索二分查找需要排序，python的list已帶有排序函數(shù)，采用的是快速排序法，時間復(fù)雜度為O(nlogn)。A=[34,6,19,14,20,4,88]A.sort()#從小到大排序A.sort(reverse=True)#重大到小排序這個開銷是否合算呢？如果只需要查找一次，不如直接查找。如果需要經(jīng)常從一個很長的序列中進行查找，不如事先花點時間排好序，以后就可以一勞永逸地利用二分法查找了。排序的開銷案例1：二分法

查找數(shù)字和2PART給定1萬個數(shù)字，從中找出兩個數(shù)，使得兩個數(shù)的和恰好等于一個指定的數(shù)X，輸出這2個數(shù)的值（可能找不到）。前面的火星車搜索礦石標本問題就是這個問題。算法1

對前面n-1個數(shù)循環(huán)（外循環(huán)），每次循環(huán)，都將這個數(shù)和它后面的數(shù)進行配對（內(nèi)循環(huán)），時間復(fù)雜度是O(n2)。算法2先排序，然后對前n-1個元素循環(huán)，每次循環(huán)時，對元素a，到后面用二分法搜索X-a，雖然排序的復(fù)雜度是O(nlogn)，但是循環(huán)的復(fù)雜度也是O(nlogn)，因此優(yōu)于算法1。二分法查找數(shù)字和importrandomrandom.seed(17)#隨機數(shù)種子，使得A里面的數(shù)固定#在1到百萬的范圍內(nèi)，生成1萬個數(shù)字A=[random.randint(1,1000000)foriinrange(10000)]X=37711#要搜索的數(shù)字和founded=Falseforiinrange(len(A)-1):#遍歷前n-1個數(shù)

forjinrange(i+1,len(A)):ifA[i]+A[j]==X:print(A[i],A[j])founded=Truebreak#會跳到下一個breakelse:continue#沒有break就到這里執(zhí)行

break#確保退出外循環(huán)ifnotfounded:print('沒找到')時間復(fù)雜度為O(n2)i7機器耗時8秒算法1：使用循環(huán)importrandomrandom.seed(17)#隨機數(shù)種子，使得A里面的數(shù)固定#在1到百萬的范圍內(nèi)，生成1萬個數(shù)字A=[random.randint(1,1000000)foriinrange(10000)]A.sort()#nlognX=37711#要搜索的數(shù)字和founded=Falsefori,ainenumerate(A[:-1]):#遍歷前n-1個數(shù)

idx=binary_search(A[i+1:],X-a)#lognifidx!=-1:print(a,A[i+1+idx])founded=Truebreakifnotfounded:print('沒找到')時間復(fù)雜度O(nlogn)馬上出結(jié)果算法2：使用二分法案例2：二分法

求方程的根3PART求一元一次方程、一元二次方程的根：ax+b=0,ax2+bx+c=0用公式求解。一元n（n>=3）次方程呢？x3-5x2+10x-80=0非多項式方程呢？xex-1=0二分法求方程的根f(x)=x3-5x2+10x-80=0，若求出的根是a，則要求|f(a)|<=10-5。對f(x)求導(dǎo)，得f'(x)=3x2-10x+10。由一元二次方程求根公式知方程f'(x)=0無解，因此f'(x)恒大于0。故f(x)是單調(diào)遞增的。這種單調(diào)性說明方程只有一個根。二分法求方程的根importnumpyasnpimportmatplotlib.pyplotaspltx=np.linspace(-20,20)y=x**3-5*x**2+10*x-80#設(shè)置橫軸縱軸刻度范圍plt.axis([-20,20,-500,500])plt.grid('on')#繪制網(wǎng)格plt.plot(x,y)plt.show()刻度范圍可以不斷嘗試，務(wù)必讓曲線穿過橫軸，以此來觀察根的大致范圍繪制函數(shù)的圖像觀察圖像，易知f(0)<0且f(10)>0,所以區(qū)間[0,10]內(nèi)必然有且只有一個根。如何找出這個根？思路1：從0開始嘗試，每次給x一個小的增量，計算y的值，|y|應(yīng)當逐步減小，當|y|開始增加時，上一個值就是解。

相當于在[x1,x2]區(qū)間內(nèi)，以某個間隔delta產(chǎn)生(x2-x1)/delta個值，然后找出其中使得f(x)滿足條件的值。存在的問題：A這個增量必須足夠小，否則可能會不滿足條件：|f(a)|<=10-5B需要循環(huán)的次數(shù)可能超出你的想象。算法1：使用循環(huán)E=1e-5x=0#改成5.7比較快delta=1E-6#x的增量whileTrue:x+=deltay=x**3-5*x**2+10*x-80print('x=',x,'y=',y)ifabs(y)<=E:break運行將近5分鐘后才得出結(jié)果：x=5.705086000000711y=3.547089164612771e-06算法的問題：1delta選得過小時，可能會進入死循環(huán)，因為不滿足退出循環(huán)的條件。2x的初值距離結(jié)果越遠，需要的時間越長，每多間隔1個單位，需要多循環(huán)1/delta次。算法1：使用循環(huán)問題規(guī)模

顯然，[x1,x2]區(qū)間內(nèi)，存在(x2-x1)/delta個值要嘗試（當然嘗試可能因為找到結(jié)果而在中途停止），因此，問題規(guī)模就是n=(x2-x1)/delta；delta的取值與E和方程的形式相關(guān)。時間復(fù)雜度

這個算法的時間復(fù)雜度顯然就是O(n)。算法1：使用循環(huán)f(x)=x**3-5*x**2+10*x-801

根在區(qū)間[0,10]當中，嘗試計算f(5)；5=(0+10)/22f(5)=-56<0,根在區(qū)間[5,10]當中，嘗試計算f(7.5)；7.5=(5+10)/23f(7.5)=135.625>0,根在區(qū)間[5,7.5]當中，嘗試計算f(6.25)；6.25=(5+7.5)/24f(6.25)=31.328125>0,根在區(qū)間[5,6.25]當中，嘗試計算f(5.625)；5.625=(5+6.25)/25f(5.625)=-3.974609375<0,根在區(qū)間[5.625,6.25]當中，嘗試計算f(5.9375)；5.9375=(5.625+6.25)/2算法2：使用二分法6f(5.9375)=12.42…>0,根在區(qū)間[5.625,5.9375]當中，嘗試計算f(5.78125)；5.78125=(5.625+5.9375)/27f(5.78125)=3.92…>0,根在區(qū)間[5.625,5.78125]當中，嘗試計算f(5.703125)；5.703125=(5.625+5.78125)/2…….顯然，上述過程是計算機最擅長的：不斷重復(fù)的枯燥的過程。算法2：使用二分法E=1e-5x1,x2=0,10y=1#隨意的較大的初值whileabs(y)>E:x=(x1+x2)/2y=x**3-5*x**2+10*x-80ify>=0:x2=xelse:x1=xprint('x=',x,'y=',y)算法2：使用二分法對于區(qū)間[x1,x2]，每次循環(huán)后，區(qū)間變?yōu)閇x1,(x1+x2)/2]或[(x1+x2)/2,x2]，區(qū)間都會縮小為原來的一半。因此，區(qū)間[x1,x2]中需要嘗試的值的數(shù)目為n=(x2-x1)/delta，二分法求根的時間復(fù)雜度為O(logn)算法2：使用二分法對于非單調(diào)函數(shù)，怎么處理？

可以繪圖考察曲線的形狀，觀察不同的根所在的單調(diào)區(qū)間，然后分別指定區(qū)間來求不同的根例如：f(x)=x4-5x2+10x-80=0由右圖可知，2個根分別在下面單調(diào)區(qū)間中：[-5,-2.5]，[2.5,5.0]需要注意的是：對于單調(diào)下降區(qū)間，前面的程序需要修改為：ify>=0:x1=xelse:x2=x思考一下，為什么要這樣修改？非單調(diào)函數(shù)處理方法案例3：求和問題4PART給定4組數(shù)（元素總數(shù)n相同，n<=100），在每組數(shù)中找一個數(shù)，使得4個數(shù)之和為0，求共有多少組數(shù)符合條件（不同的索引號算不同的結(jié)果）。例如：[-45,-41,-36,-36,26,-32][22,-27,53,30,-38,-54][42,56,-37,-75,-10,-6][-16,30,77,-46,62,45]結(jié)果為：5這5組數(shù)為：

(-45,-27,42,30),(26,30,-10,-46),(-32,22,56,-46),(-32,30,-75,77),(-32,-54,56,30).求和問題最容易想到的思路是暴力求解，即設(shè)計4重循環(huán)，對每種可能的組合進行求和，每當和為0時，計數(shù)器加1即可。暴力法的時間復(fù)雜度為O(n4)，n為100時，循環(huán)108次，估算時間為102秒（循環(huán)106算1秒）。算法1：使用循環(huán)為減少時間，設(shè)置n為100，循環(huán)次數(shù)為108，觀察下大約需要多久(結(jié)果為3302)importrandomrandom.seed(7)#固定隨機數(shù)種子，每次產(chǎn)生相同序列A,B,C,D=[],[],[],[]n=100foriinrange(n):A.append(random.randint(-10000,10000))B.append(random.randint(-10000,10000))C.append(random.randint(-10000,10000))D.append(random.randint(-10000,10000))result=0foriinrange(n):forjinrange(n):forkinrange(n):forlinrange(n):ifA[i]+B[j]+C[k]+D[l]==0:result+=1print('result=',result)算法1：使用循環(huán)解題思路：考慮若4個數(shù)a+b+c+d=0,則a+b=-(c+d)。如果找出所有的a+b，放入一個列表X，對于任一個-(c+d)，若能在X中找到，則存在1個解，而搜索的過程可以利用二分法提高效率。1對列表A和B進行所有可能的求和，將結(jié)果放入列表X，對X排序。2對列表C和D進行所有可能的求和，求和結(jié)果取負數(shù)，記為key，然后用二分法在X中搜索key，如果找到，則存在一組數(shù)據(jù)的和為0。時間復(fù)雜度，對n2個元素排序：O(n2log(n2))=O(n2log(n))n=100時，循環(huán)次數(shù)<105，時間不到1秒。算法2：使用二分法有問題的代碼X=[]result=0foriinrange(n):forjinrange(n):X.append(A[i]+B[j])X.sort()foriinrange(n):forjinrange(n):key=-(C[i]+D[j])

idx=binary_search(X,key)ifidx!=-1:result+=1print('result=',result)結(jié)果為：2738和前面的暴力法結(jié)果不相同。通過分析可知，X中可能存在一些相同的數(shù)，因此可能會漏掉一些結(jié)果。算法2：使用二分法解決方案改進二分搜索函數(shù)，使其返回2個索引號，分別指示找到的第一個和最后一個元素的索引號，記為p1,p2，則每次二分搜索之后，result+=(p2-p1+1)。例如，在下面的序列中搜索12：3,6,9,12,12,12,18,20返回：3,5則解的總數(shù)增加(5-3+1)=3算法2：使用二分法修改二分搜索函數(shù)每次找到x，都嘗試向前搜索，直到找到最前面的x為止；再嘗試向后搜索，直到找到最后面的x為止。defbinary_search1(A,x):i,j=0,len(A)-1whilei<=j:k=(i+j)//2ifx==A[k]:p1=p2=kwhilep1>0andA[p1-1]==x:p1-=1whilep2<len(A)-1andA[p2+1]==x:p2+=1returnp1,p2elifx<A[k]:j=k-1el