二分查找及其應(yīng)用

1、二分查找及其應(yīng)用第一頁，共20頁。今天，你今天，你ACAC了嗎？了嗎？NO!YES!請在這里輸入您的標(biāo)題第二頁，共20頁。刷題太無聊？我們玩游戲吧！相信大家都玩過猜數(shù)字的相信大家都玩過猜數(shù)字的游戲。兩人游戲，游戲。兩人游戲，A同學(xué)在心同學(xué)在心里默念一個整數(shù)里默念一個整數(shù)n（1 = n = 1000）。）。B同學(xué)猜同學(xué)猜n是多少。是多少。同時如果同時如果B沒有猜對，沒有猜對，A告訴告訴他這個數(shù)比默念的數(shù)高了還他這個數(shù)比默念的數(shù)高了還是低了。是低了。第三頁，共20頁。最壞情況下需要多少次呢？第四頁，共20頁?？雌饋砗脜柡Φ臉幼?其實并不是，下面將引入其實并不是，下面將引入“二分二分搜索搜索”的概念

2、。的概念。 如上述的游戲中，第一次應(yīng)該取如上述的游戲中，第一次應(yīng)該取多少呢？多少呢？ 500！ 很不巧并不是很不巧并不是500，而是一個比，而是一個比500大的數(shù)。大的數(shù)。 雖然運氣不好，但是雖然運氣不好，但是B將區(qū)間的范將區(qū)間的范圍砍掉了一半！圍砍掉了一半！ 那么下一次那么下一次B該猜什么。該猜什么。第五頁，共20頁。大家已經(jīng)發(fā)現(xiàn)，問題變成了501-1000之間猜一個數(shù)，那么應(yīng)該猜(501+1000)/2 = 750!如果運氣還是不好，又猜小了.沒關(guān)系！只猜了僅僅兩次，我們就將區(qū)間縮小為 751-1000.那么繼續(xù)下去.第六頁，共20頁。我們發(fā)現(xiàn)，每次可以將區(qū)間縮小為原來的一半。遞減速度顯然

3、就是log級別的。log(1000)向上取整只有10.那么我們一定可以在10次之內(nèi)猜出這個數(shù)。第七頁，共20頁。給定一個有序序列a0,a1,a2.aN，給出一個目標(biāo)值tg，在序列中查找是否存在tg，如果存在，返回tg的下標(biāo)。如何快速查找？第八頁，共20頁。我們必須看到數(shù)列是有序的 充分利用有序的條件，類似猜數(shù)充分利用有序的條件，類似猜數(shù)一樣查找一樣查找tg。 復(fù)雜度為復(fù)雜度為log(n)。 那么我們來看看如何實現(xiàn)二分查找那么我們來看看如何實現(xiàn)二分查找。第九頁，共20頁。int bs(int *a, int n, int tg) int l = 0, r = n-1; while(l tg) r

4、 = mid-1; else l = mid+1; return -1;第十頁，共20頁。二分查找的應(yīng)用（二分答案） 假定一個解判斷是否可行假定一個解判斷是否可行 最大化最小值最大化最小值 最大化平均值最大化平均值第十一頁，共20頁。有N條繩子，它們長度分別為Li。如果從他們中切割出K條長度相同的繩子的話，這K條繩子每條最長能有多長？答案保留兩位小數(shù)。 1=N=104, 1=K=104, 1=Li n k; for(int i = 0; i ai; double l = 0, r = 100001; for(int i = 0; i 100; i+) double m = (l+r)/2; i

5、f(ok(m) l = m; else r = m; printf(%.2fn, 0.01 * (int)(l*100) ); return 0;int n, k;double amaxn, tot = 0;bool ok(double x) int num = 0; for(int i = 0; i = k) return true; return false;第十四頁，共20頁。再看一道最大化最小值的例題這類問題通過二分搜索可以很好的解決。第十五頁，共20頁。農(nóng)夫約翰搭了一間有N間牛社的小屋。牛舍排在一條直線上，第i號牛舍在xi的位置，但是他的M頭小牛對小屋很不滿意，因此經(jīng)常互相攻擊。約翰

6、為了防止牛之間互相傷害，因此決定把每頭牛都放在離其他牛盡可能遠的牛舍。也就是最大化最近的兩頭牛之間的距離。第十六頁，共20頁。條件限制：2=N=1000002=M=N0=xi n c; for(int i = 0; i posi; sort(pos, pos+n); int l = 0, r = MAX+1; while(r - l 1) int m = (l+r) 1; if(ok(m) l = m; else r = m; cout l endl; return 0;int n, c;int posmaxn;bool ok(int ma) int cnt = 1; int last = 0; for(int