二分
二分的模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 //模板一 int bsearch1(int l, int r){ while (l < r){ int mid = (l + r ) / 2; if(check(mid)) r = mid; else l = mid + 1 ; } return l; } // 对于很大的数据,l+r 可能会溢出，可写成 l+(r-1>>1) // 模板二 int bsearch2(int l, int r) { while (l < r){ int mid = (l + r + 1) / 2; if(check(mid)) l = mid; else r = mid -l; } return r; } // 模板三（掌握） int bsearch3(int l,int r) { int ans = 0; while(l <= r) { int mid = (l+r) / 2; if(check(mid) ) { ans = mid; l = mid + 1;} else r = mid - 1; } return ans; } // 浮点二分 double bsearch4(double l, double r) { const double eps = 1e-6; while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; // check()判断mid是否满足性质 else r = mid - 1; // 如果mid不满足性质，则将其从搜索区间中去除 } } 第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。 只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一； 只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一； ...