主题Binarysearch二分搜寻.pptVIP

*主題:Binarysearch(二分搜尋)解題技巧SearchLinearSearchBinarySearch例題講解歷年題目*什麼是search？在一堆資料中，找出需要的東西例:在名單中找看看有沒人叫“王小明”在一堆數字中，最接近50的數字是多少Linearsearch最簡單、直覺的方法，把所有的東西都看過一次，找出需要的東西在資料沒有被特殊處理過的情況下，這也是唯一的search方法要是資料並不是sorted順序1~100之中猜數字在資料是sorted的順序自己把資料sort一次什麼情況下能用binarysearch呢？*原理因為資料是已經排好順序的，所以每次查詢時，從中間的地方去查一次，就可以判斷哪一半的人是不符合要求的，一次可以排除一半的候選人98765432110151413121116要猜的數字太小太小太大目前還有機會被選到的下限4Test_function()5Upperbound1目前還有機會被選到的上限2Lowerbound3給一個值去做測試，能return說比這個值大的還是小的那邊是還有機會的61猜數字，範圍1~16(假設答案為10)2上限16，下限1，猜8時，Test_function會回答太小==下限改為93上限16，下限9，猜12時，Test_function會回答太大在一個總個數為n，sorted的資料中做binarysearch總共要log2n次的test01長度160216/2=8;8/2=4;4/2=2;2/2=1;03log216=4;04要是給的資料不是一個sorted的狀態，要不要先sort再做binarysearch？01如果只需要在資料中做少量的search，就不要sort，直接做linearsearch就好02如果需要很多次的search，先sort會有利03如果只會問很少次每次做linearsearch如果會問很多次先把數字sort一次，每次問的時後做binarysearch給一堆數字，問某個數字在不在這堆數字之中給一堆整數，請找最大的一個數字d使得a+b+c=d，其中abcd是這堆數字中的某四個不同的數字每個數字的範圍在-536870912~536870911總共最多有1000個數字a+b+c總共會有1000*1000*1000種可能01將等式換成a+b=d–c02a+b和d–c各只有1000*1000種可能03把所有可能的a+b都算出來，sort一次，之後把所有可能的d–c去之前a+b所產生的list中做binarysearch04Input2,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每個數字去做binarysearch解下面的方程式(給定p,q,r,s,t,u，求x)p*e-x+q*sin(x)+r*cos(x)+s*tan(x)+t*x2+u=0, where0=x=1,0=p,r=20and-20=q,s,t=0輸出到小數點以下第四位在0=x=1中，p*e-x,cos(x)為遞減的方程式q*sin(x),s*tan(x),t*x2為遞增的方程式加上0=p,r=20and-20=q,s,t=0的條件後，整個式子為一個遞減的方程式任意帶兩點x1,x2進遞增(減)方程式中，若f(x1)*f(x2)0，則在x1到x2之中一定有一個點x3使得f(x3)=0設upper=1，lower=0，mid=(upper+lower)/2,若f(mid)的值很小或等於0的話，mid就是方程式的根，否則則看f(mid)*f(upper)和f(mid)*f(lower)哪個值小於0，則往那個方向做binarysearch|upper–lowe