二分搜索——不光是查找值

基本思想

　　二分搜索法的基本思想是通过不断的缩小解可能存在的范围，从而求得问题最优解的方法。比如一个直观的问题是在一个由小到大的数列a中找到一个数ai，使得ai满足ai>=k的同时，i最小。由于此数列是有序的，所以找到中间位置的数amid和k比较，如果k<=amid，证明k在左半区域，区间左边界变为mid，否则在右半区域,区间右边界变为mid。如此下来，直至区间长度小于1，结束循环，最小的i就是右边界的值。

　　二分搜索的优势在于时间上的高效，每次去掉一半的搜索区间，可以在O(logn)的时间复杂度求得最终的解。但是这种高效是建立在事先将数排好序的基础上的。

　  实现原理

　　反复与区间的中点进行比较，不断的将解的范围缩小到原来的一半，直至满足一定的条件后结束算法。简单起见，直接看一道VJudge上的例题Lower Bound ，具体细节参考如下代码：

 1 #include <cstdio> 2  3 const int maxn = 100000 + 10; 4 int a[maxn]; 5 int n, q; 6  7 void query(int k) { 8     int lb = -1, ub = n;//初始化区间短点  9     while(ub - lb > 1) {//结束条件是当区间的长度小于1的时候 10         int mid = (ub + lb) / 2;11         //通过判断缩小区间为原来的一半 12         if(a[mid] >= k)13             ub = mid;14         else15             lb = mid;16     }17     18     printf("%d\n", ub);19 }20 21 int main()22 {23     while(scanf("%d", &n) != EOF) {24         for(int i = 0; i < n; i++) {25             scanf("%d", &a[i]);26         }27         28         scanf("%d", &q);29         while(q--) {30             int k;31             scanf("%d", &k);32             query(k);//查询k 33         }34     }35     return 0;36 }

　　当然C++中的STL以lower_bound函数的形式实现了二分搜索，直接可以调用。参考代码如下：

 1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5  6 const int maxn = 100000 + 10; 7 int n, q; 8 vector<int> v; 9 10 int main () {11     while(scanf("%d", &n) != EOF) {12         v.clear();13         for(int i = 0; i < n; i++) {14             int tmp;15             scanf("%d", &tmp);16             v.push_back(tmp);17         }18         19         scanf("%d", &q);20         while(q--) {21             int k;22             scanf("%d", &k);23             24             printf("%d\n", lower_bound(v.begin(), v.end(), k) - v.begin());25         }26     }    
27     return 0;28 }

　　在编程竞赛中的典型应用

　　二分搜索算法除了在有序数组中查找值之外，在求解最优解的问题上也非常有用。比如求满足某个条件C(x)的最小x,我们可以假定一个区间，取该区间的中点值为mid，如果满足C(mid)，左边界等于区间中点，即将范围缩小在右侧（最大化），如果不满足，那么右边界等于区间中点，即将范围缩小在左侧。直到将区间缩小到一定的程度后，在此精度下的问题最优解就求出来了。

　　1.假定一个解并判断是否可行，例如POJ 1064 Cable master

　　2.最大化最小值，例如POJ 2456 Aggressive cows

　　3.最大化平均值，例如POJ 3111 K Best

　　例题解析

　　POJ 1064 Cable master

　　有N条绳子，长度分别是Li，如果从它们中切割出K条长度相同的绳子的话，每条绳子最长是多少

　   我们将区间设为0到INF（最大），然后尝试区间的中点，向满足条件的最大值逼近（循环100次精度大概是1e-30）。条件C(x)：Li/x的总和是否大于K，代码如下：（坑点是最后输出保留两位小数，不进位）

 1 #include <cstdio> 2 #include <cmath> 3 const int maxn = 10000 + 10; 4 const int inf = 99999999; 5  6 int N, K; 7 double L[maxn]; 8  9 bool C(double x) {10     int num = 0; 
11     for(int i = 0; i < N; i++) {12         num += (int)(L[i] / x);13     }14     return num >= K;15 }16 void solve() {17     double lb = 0, ub = inf;18     for(int i = 0;i < 100; i++) {19         double mid = (ub + lb) / 2;20         if(C(mid))21             lb = mid;22         else 23             ub = mid;24     }25     26     printf("%.2f\n", floor(ub * 100) / 100);27 }28 int main()29 {30     while(scanf("%d%d", &N, &K) != EOF) {31         for(int i = 0; i < N; i++) {32             scanf("%lf", &L[i]);33         }34         35         solve();36     }    
37     return 0;38 }

　　POJ 2456 Aggressive cows

　　将M头牛放在N个牛舍里，使得这M头牛之间的举例尽可能的大。

　　意即求解满足C(d)的最大d。而其中的d表示M头牛之间的举例均不小于d。区间的结束条件就是区间长度大于等于1，关键是如何判断满足条件，其实也好判，采用贪心的方法，一次往后使用即可，如果M头牛安排完了，满足，否则不满足。代码如下：

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4  5 const int maxn = 100000 + 10; 6 const int inf = 1000000000 + 10; 7 int N, M; 8 int x[maxn]; 9 10 bool C(int d) {11     int last = 0; 
12     for(int i = 1; i < M; i++) {13         int crt = last + 1;14         while(crt < N && x[crt] - x[last] < d) {15             crt++;16         }17         18         if(crt == N)    return false;19         last = crt;20     }21     return true;22 }23 void solve() {24     sort(x, x + N);25     26     int lb = 0, ub = inf;27     while(ub - lb > 1) {28         int mid = (ub + lb) / 2;29         if(C(mid))30             lb = mid;31         else32             ub = mid;33     }     
34     35     printf("%d\n", lb);36 }37 int main()38 {39     while(scanf("%d%d", &N, &M) != EOF) {40         for(int i = 0; i < N; i++) {41             scanf("%d", &x[i]);42         }43         44         solve();45     }46     return 0;47 }

　　POJ 3111 K Best

　　有n个物品的价值和重量分别是vi和mi，从中选出k件物品使得单位重量的价值最大。

　　C(x)=（(vi - x * wi) 从大到小排列中的前k个的和不小于0）

　　精度1e-30

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4  5 const int maxn = 100000 + 10; 6 const double inf = 0x3f3f3f3f; 7 const double EPS = 1.0e-6; 8  9 int N, K;10 int v[maxn], w[maxn];11 struct Node {12     double val;13     int id;14 } y[maxn];15 16 bool cmp(struct Node a, struct Node b) {17     return a.val > b.val;18 }19 bool C(double x) {20     for(int i = 0; i < N; i++) {21         y[i].id = i + 1;22         y[i].val = (v[i] - x * w[i]);23     }24     25     sort(y, y + N, cmp);26     double sum = 0;27     for(int i = 0; i < K; i++) {28         sum += y[i].val;29     }30     return sum >= 0;31 }32 void solve() {33     double lb = 0, ub = inf;34     35     while(ub - lb > EPS) {36         double mid = (ub + lb) / 2;37         if(C(mid))38             lb = mid;39         else40             ub = mid;41     }    
42     43     for(int i = 0; i < K - 1; i++) {44         printf("%d ", y[i].id);45     }46     printf("%d ", y[K - 1].id);47 }48 49 int main()50 {51     while(scanf("%d%d", &N, &K) != EOF) {52         for(int i = 0; i < N; i++) {53             scanf("%d%d", &v[i], &w[i]);54         }55         56         solve();57     }    
58     return 0;59 }

　　至此，二分搜索算法就讲完了，二分的思想就是一次去一半，寻找满足条件的最优，在解决最优解问题的时候要找好结束条件和满足的条件。算法不难，关键是思考问题和实现算法的过程。

 原文出处：https://www.cnblogs.com/wenzhixin/p/9630277.html