首页 > 代码库 > 二分怎么写
二分怎么写
主要参考这个https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/讲的非常仔细。
以前做题的时候，经常遇到一些二分的题目，但是对边界条件，主要是加一还是减一，把握的不是很准确，后来看到别人推荐的上面的链接，终于不再迷茫了。
这里需要注意几点：
1.一般二分的情况，准确寻找一个数，求满足条件的最大值，求满足条件的最小值。尤其注意求满足条件的最大值，防止进入死循环，需要进行2个数的情况测试。
原文中描述如下：
The code will get stuck in a loop. It will always select the first element as mid, but then will not move the lower bound because it wants to keep the no in its search space. The solution is to change mid = lo + (hi-lo)/2 to mid = lo + (hi-lo+1)/2, i.e. so that it rounds up instead of down. There are other ways of getting around the problem, but this one is possibly the cleanest. Just remember to always test your code on a two-element set where the predicate is false for the first element and true for the second.
2.再就是使用二分法注意的条件，这也是判断一个题目是否能够使用二分法的关键条件，如果要说解题需要什么套路的话，我感觉这就是套路。下面的黑体字，每一点说的都是非常重要的。
As you see, we used a greedy algorithm to evaluate the predicate. In other problems, evaluating the predicate can come down to anything from a simple math expression to finding a maximum cardinality matching in a bipartite graph.
Conclusion
If you’ve gotten this far without giving up, you should be ready to solve anything that can be solved with binary search. Try to keep a few things in mind:
- Design a predicate which can be efficiently evaluated and so that binary search can be applied
- Decide on what you’re looking for and code so that the search space always contains that (if it exists)
- If the search space consists only of integers, test your algorithm on a two-element set to be sure it doesn’t lock up
- Verify that the lower and upper bounds are not overly constrained: it’s usually better to relax them as long as it doesn’t break the predicate
1 #include<bits/stdc++.h> 2 #define pb push_back 3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 5 typedef long long ll; 6 using namespace std; 7 typedef pair<int, int> pii; 8 const int maxn = 1e3 + 10; 9 int a[maxn];10 int n;11 //准确的查找一个值12 //相当于stl里面的 binary_search()13 int bin_ser(int tar) {14 int left = 0, right = n - 1;15 while(left <= right) {16 int mid = left + (right - left) / 2;17 if(a[mid] == tar) return mid;18 else if(a[mid] < tar) left = mid + 1;19 else right = mid - 1;20 }21 return -1;22 }23 bool check(int x) {24 if(x < 10) return 1;25 return 0;26 }27 //寻找满足条件的最小值28 //相当于stl的 lower_bound()29 int low_ser() {30 int left = 0, right = n - 1;31 while(left < right) {32 int mid = left + (right - left) / 2;33 if(check(mid)) {34 right = mid;35 } else left = mid + 1;36 }37 if(!check(left)) return -1;38 return left;39 }40 //寻找满足条件的最大值41 //比较常用，容易出bug，需要对2个数的情况进行判断42 int up_ser() {43 int left = 0, right = n - 1;44 while(left < right) {45 int mid = left + (right - left + 1) / 2;46 if(check(mid)) left = mid;47 else right = mid - 1;48 }49 if(!check(left)) return -1;50 return left;51 }52 //还有对实数的二分，一般是达到要求的精度或者是迭代一定的次数53 //然后得到想要的答案。54 const double eps = 1e-8;55 double bin_se() {56 double left = 0, right n - 1;57 while(right - left > eps) {58 double mid = left + (right - left) / 2;59 if(check(mid)) {60 right = mid;61 } else left = mid;62 }63 return left;64 }65 void solve() {66 67 }68 int main() {69 freopen("test.in", "r", stdin);70 //freopen("test.out", "w", stdout);71 solve();72 return 0;73 }
二分怎么写