《主题Binarysearch二分搜寻.ppt》由会员分享，可在线阅读，更多相关《主题Binarysearch二分搜寻.ppt（32页珍藏版）》请在三一办公上搜索。
1、1,主題:Binary search(二分搜尋),解題技巧SearchLinear SearchBinary Search例題講解歷年題目,2,什麼是 search？,在一堆資料中，找出需要的東西例:在名單中找看看有沒人叫“王小明”在一堆數字中，最接近50的數字是多少,3,Search 方法,Linear search最簡單、直覺的方法，把所有的東西都看過一次，找出需要的東西在資料沒有被特殊處理過的情況下，這也是唯一的 search 方法,4,Binary search,什麼情況下能用 binary search 呢？在資料是 sorted 的順序1100 之中猜數字要是資料並不是 sorte
2、d 順序自己把資料 sort 一次,5,Binary search,原理因為資料是已經排好順序的，所以每次查詢時，從中間的地方去查一次，就可以判斷哪一半的人是不符合要求的，一次可以排除一半的候選人,9,8,7,6,5,4,3,2,1,10,15,14,13,12,11,16,太小,太小,太大,6,Binary search,Upper bound目前還有機會被選到的上限Lower bound目前還有機會被選到的下限Test_function()給一個值去做測試，能 return 說比這個值大的還是小的那邊是還有機會的,7,Example,猜數字，範圍 1 16(假設答案為 10)上限 16，下
3、限 1，猜 8 時，Test_function 會回答太小=下限改為 9上限 16，下限 9，猜 12 時，Test_function 會回答太大,8,Binary search 的速度,在一個總個數為 n，sorted 的資料中做 binary search 總共要 log2 n 次的 test長度 1616/2=8;8/2=4;4/2=2;2/2=1;log2 16=4;,9,Binary search V.S.Linear search,要是給的資料不是一個 sorted 的狀態，要不要先 sort 再做 binary search？如果只需要在資料中做少量的 search，就不要 so
4、rt，直接做 linear search 就好如果需要很多次的 search，先 sort 會有利,10,應用:找數字,給一堆數字，問某個數字在不在這堆數字之中如果只會問很少次每次做 linear search如果會問很多次先把數字 sort 一次，每次問的時後做 binary search,11,Problem:A.10125,給一堆整數，請找最大的一個數字 d 使得 a+b+c=d，其中 a b c d 是這堆數字中的某四個不同的數字每個數字的範圍在-536870912 536870911總共最多有 1000 個數字,12,解法,a+b+c 總共會有 1000*1000*1000種可能將等
5、式換成 a+b=d c a+b 和 d c 各只有1000*1000 種可能把所有可能的 a+b 都算出來，sort 一次，之後把所有可能的 d c 去之前 a+b 所產生的 list 中做 binary search,13,Sample,Input2,3,5,7,12任兩個數字和的所有可能5,7,9,14,8,10,15,12,17,19sort 之後:5,7,8,9,10,12,14,15,17,19任兩個數字差的所有可能12 2,12 3,12 5,3 2 每個數字去做 binary search,14,應用:方程式求根(A.10341),解下面的方程式(給定 p,q,r,s,t,u，求
6、 x)p*e-x+q*sin(x)+r*cos(x)+s*tan(x)+t*x2+u=0,where 0=x=1,0=p,r=20 and-20=q,s,t=0輸出到小數點以下第四位在 0=x=1中，p*e-x,cos(x)為遞減的方程式q*sin(x),s*tan(x),t*x2 為遞增的方程式加上 0=p,r=20 and-20=q,s,t=0 的條件後，整個式子為一個遞減的方程式,15,解法,任意帶兩點 x1,x2 進遞增(減)方程式中，若 f(x1)*f(x2)0，則在 x1 到 x2 之中一定有一個點 x3 使得f(x3)=0設 upper=1，lower=0，mid=(upper+
7、lower)/2,若f(mid)的值很小或等於 0 的話，mid 就是方程式的根，否則則看 f(mid)*f(upper)和 f(mid)*f(lower)哪個值小於 0，則往那個方向做 binary search|upper lower|10-6 可停下,16,lower,upper,mid,17,應用:開次方,給兩個數 n 和 p，求 為多少,18,解法,用 binary search，並將題目轉換為 ap=n，給定 n 和 p，求 a=？115 6541328 1015115 6541328 5.515,19,求 ap,p 有可能非常大若是每次乘以 a 的話要乘以非常多次速度會很慢1.2
8、21=1.2*1.2*1.2*1.2,21 次,20,p=21d=24+22+20=10101ba21=a16 a4 a1ap 只需要 log2 p 次的平方和加法就可以求得double power(double a,int p)double s=1;while(p 0)if(p%2)=1)/check the rightmost bits=s*a;a=a*a;/repeat squaringp=p/2;/shift-right one bitreturn s;,21,應用:求所有次方根,給定 n，試求出所有可能的 a 和 p 使得 ap=n，其中 p 為整數Hint:對每個有可能的 p，去
9、binary search 相對應的 a 為多少,22,應用:大數除法,除法的動作麻煩，利用 binary search 的方法，只需要大數乘法，大數加法，大數比較，和一個大數除以 2 的動作，就可以得到除法的結果,23,例題講解:H.91.3 侏儸紀公園,公園內分兩個地方，旅客都會先到恐龍博物館再到探險公園，旅客逛博物館的時間不一樣逛博物館的時間決定了旅客到達探險公園的順序探險公園會提供單人客車，每部車搭載一人，旅客先到先上車若是車子都已出發，則旅客必須等待。如果車子空著等待載客卻沒有客人，車子就必須等待如果旅客等超過 30 分鐘，則會放棄等待離開,24,已知條件為下旅遊團的旅客數量 m(6
10、0=m=10)每位旅客逛博物館的分鐘數 t(60=t=1)每位旅客搭車逛探險公園的分鐘數 T(60=T=1)問至少需要幾部單人客車，才能滿足所有的旅客(不必因為等待太久而放棄搭車),25,Sample,5 30 5 10 10 40 15 10 30 20 35 5 35 540 30 45 5 50 5 50 30,15 分時回來,35 分時回來,55 分時回來,45 分時回來,65 分時回來,60 分時回來,65 分時回來,95 分時回來,70 分時回來,75 分時回來,105 分時回來,26,解法(I),照著題目的意思做，有人來的時後如果沒有車子而且 30 分鐘內也不會有車子回來的話就多
11、開一台車給他，若是 30 分鐘內有車子回來的話就等example 1 30 新開一台車 A 2 30 A 車 31 分時會回來 等它 3 35 A 車 61 分時才會回來，不等，開新車 B 4 35 B 車 38 分時才會回來，不等，開新車 C總共需要三台車,27,Wrong!較好的分法 1 30 新開一台車 A 2 30 A 車 31 分時會回來，但不等，開新車 B 3 35 A 車 31 分時才會回來，等它 4 35 B 車 32 分時才會回來，等它只需兩台車就夠了,28,解法(II):binary search,剛剛解法(I)會出錯是因為當有人來的時後，我們不知道要讓他等前面的車回來或是
12、直接多開一台車給他比較好但是如果已經決定了總共要開幾台車的話，如果有車空下來，旅客坐上去一定不會吃虧，要是沒有車空下來，就只好等車回來,29,解法(II):binary search,對總共需要的車數做 binary search!比如說旅客總共有 10 個人則去測 5 台車夠不夠，如果不夠，那 8 台車夠不夠，依此類推,30,upper_bound一開始設為旅客總人數一人一台一定夠用lower_bound一開始設為一台最少也得開一台車Test_function給定要開幾台車時，去模擬以這些數量的車夠不夠符合題目的要求,31,Program structure,initialize();whi
13、le(upper_bound!=lower_bound)mid=(upper_bound+lower_bound)/2;Test_function(mid);if enough()upper_bound=mid;elselower_bound=mid+1;,32,歷年題目,練習題A.10341 Solve ItA.10125 Sumsetshttp:/acm.uva/es/p/v101/10125.htmlA.10567 Helping Fill Bateshttp:/acm.uva/es/p/v105/10567.htmlA.714 Copying Books挑戰題2004兩岸清華學生程式比賽 Problem B,Dhttp:/venus.cs.nthu.edu.tw/jous/NTHU2004-Problems.docNTHU2004-Problems.docA.10212 The Last Non-zero Digit其它歷年題目無,
