做了九度1502後，發現自己對二分查找越來越不了解了，特别是各種邊界情況，left = mid還是left = mid + 1 ? right = mid 還是 left = mid-1 ? return left ,return mid還是return right？仔細研究後發現這裡面大有玄機。于是寫下一點點心得體會，免得以後忘記了。 在劉汝佳大神的《算法競賽入門經典》中的二分查找是這樣的
int bsearch(int* A, int x, int y, int v)
{
while(x < y)
{
m = x + (y-x)/2;
if(A[m] == v) //A[]是待查找數組, v是要查找的值
return m;
else if(A[m] > v)
y = m;
else
x = m+1;
}
return -1;
}
一開始并沒有太深入探究為什麼要這樣寫(每次如何更新x和y的值，最後傳回的值等等)，隻是大概知道二分的工作方式就是每次縮減一般的搜尋範圍，直到最後查找的範圍很小。
但是1502令我wa了差不多二十多三十次之後，我似乎了解了為什麼要這樣寫(但貌似錯的地方不是這一部分23333).
先貼上1502的題目描述：
題目1502：最大值最小化
時間限制：1 秒
記憶體限制：128 兆
特殊判題：否
送出：533
解決：197
- 題目描述：
-
在印刷術發明之前，複制一本書是一個很困難的工作，工作量很大，而且需要大家的積極配合來抄寫一本書，團隊合作能力很重要。
當時都是通過招募抄寫員來進行書本的錄入和複制工作的, 假設現在要抄寫m本書，編号為1,2,3...m, 每本書有1<=x<=100000頁， 把這些書配置設定給k個抄寫員，要求配置設定給某個抄寫員的那些書的編号必須是連續的。每個抄寫員的速度是相同的，你的任務就是找到一個最佳的配置設定方案，使得所有書被抄完所用的時間最少。
- 輸入：
-
輸入可能包含多個測試樣例。
第一行僅包含正整數 n，表示測試案例的個數。
對于每個測試案例，每個案例由兩行組成，在第一行中，有兩個整數m和 k， 1<=k<=m<=500。 在第二行中，有m個整數用空格分隔。 所有這些值都為正且小于100000。
- 輸出：
-
對應每個測試案例，
輸出一行數字，代表最佳的配置設定方案全部抄寫完畢所需要的時間。
- 樣例輸入：
-
2 9 3 100 200 300 400 500 600 700 800 900 5 4 100 100 100 100 100
- 樣例輸出：
-
1700 200
題目的思路很明了,就是最大值最小化(我大一看過類似的題目，一直看不懂，還以為是dp一類的問題)，先猜一個數字v(範圍是最多的書的頁碼數max--總頁碼數sum。為什麼不知0 -- sum? 我還沒想到原因)，然後從左到右統計書的頁數，這裡也用了一點貪心的思想，每個人都抄不超過v頁的盡可能多的書，當超過了v後，就要給下一個人抄，直到全部書都抄完成。看需要的人數cnt， 再用cnt和輸入的k比較，如果cnt < k，說明這種方法可取；如果cnt > k 說明 需要的人數超出了上限，不可取。（這就是judge()函數的内容），
如果judge(v) == 1，那麼 每個人還可以抄更少的頁數來達到最大值最小化的目的。這裡用二分的方法提高效率。
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <cmath>
using namespace std;
const int INF = 0x7fffffff;
int a[600];
int n, k;
bool judge(int mid)
{
int cnt = 1;
int sum = 0;
for(int i = 0; i < n; ++i)
{
if(sum + a[i] <= mid)
sum += a[i];
else
{
sum = a[i];
cnt++;
}
}
return (cnt <= k);
}
int main()
{
// freopen("1.txt", "r", stdin);
int t;
cin >> t;
while(t--)
{
cin >> n >> k;
int sum = 0;
int maxx = 0;
for(int i = 0; i < n; ++i)
{
cin >> a[i];
sum += a[i];
if(maxx < a[i]) //*********①*********
maxx = a[i];
}
int lb = maxx, ub = sum; //**********⑤**********
int mid;
while(lb < ub) <span style="font-family: Arial, Helvetica, sans-serif;">//**********②***********</span>
{
mid = lb+(ub-lb)/2; <span style="font-family: Arial, Helvetica, sans-serif;">//**********③***********</span>
if(judge(mid))
ub = mid; <span style="font-family: Arial, Helvetica, sans-serif;">//**********</span><span style="font-family: Arial, Helvetica, sans-serif;">②</span><span style="font-family: Arial, Helvetica, sans-serif;">***********</span><span style="font-family: Arial, Helvetica, sans-serif;">
</span>
else
lb = mid+1; <span style="font-family: Arial, Helvetica, sans-serif;">//**********②************</span>
}
cout << lb << endl; //*********④*********
}
return 0;
}
共有7處需要注意
① 這是最不應該犯的錯誤，我把他寫成了if(maxx > a[i])。
② while(lb < ub) ，有的代碼會寫成while(lb <= ub) 或者 while(lb -1 < rb). 要注意三種不同的判斷條件時，下面對于mid的更新也是不同的。比如 0 1 2，要找2，
第一次：mid = (2+0) / 2; mid == 1 < 2
假如 lb = mid的話。第二次查找時 lb = 1, ub = 2; lb < rb, mid = (1+2)/ 2 = 1; 第三次查找時 lb = 1, ub = 2; lb < rb, mid = (1+2)/ 2 = 1，會造成死循環。
由c和c++截尾取整的特性可知，當lb 剛好比ub小1時，如果lb = mid 的話，會永遠處于同一種情況(lb + 1 = ub).
而為什麼ub 可以直接取mid？因為取整是截尾取整，跟比他大的數無關。
③ mid = lb+(ub-lb)/2; 這樣寫是為了防止lb+ub造成的溢出。
④ cout << lb << endl; 其實寫成 cout << ub << endl;也是可以的， 比如說 lb = 101 ub = 102 mid = 101, 那麼下一步lb = 101 mid= 101 ub = 102，如果101ok那麼 ub = 101.lb = 101. 如果101 不ok，那麼 lb = 102 ub = 102. 就是說無論如何 最後的lb 和 ub都是相等的因為while(lb < ub)嘛，而且不可能出現lb > rb 的情況。
但是，千萬不能寫成 cout << mid << endl; 或者 cout << mid+1 << enl;
因為 當最後 lb mid rb 分别為 1700 1700 1701 ，而答案為1700 時，輸出mid+1 = 1701 明顯是錯的
而當lb mid rb 分别為 198 199 200 ，答案為200 時，199 < 200 造成cnt > k, judge(199) == false, 下一步該是lb = mid +1 = 200 而此時 mid 的值依然是199，因為循環是while(lb < ub)，此時lb = ub== 200 ,但是mid卻還是上次循環中的199.是以輸出199 顯然是錯的。
⑤ 一開始二分查找的下界應該是maxx ,而不是0，為什麼會這樣我還沒弄清楚。
先寫到這，想到什麼後面再補充。
![leetcode_17.Letter Combinations of a Phone Number[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)