二分法

chc / 2023-05-04 / 原文

【概述】

1. 什么是二分法？

二分法(Bisection method)，即一分为二的的方法。对于在区间[a,b]上连续不断且满足f(a)*f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在区间二等分，使区间两个端点逐步逼近零点，进而得到零点的近似值的方法。

说人话：把答案所在的区间逐渐缩小，直到区间内只有答案。

比如猜数字游戏：给定一个1--100之间的正整数，让你猜。猜的过程中给出大小判断的提醒，问怎么才能快速地猜出来？最快的方法是：每次猜区间的中间点的数字。如果中间点大于给定数字，下次就猜前半部分的中间点数字；如果中间点数字小于给定数字，下次就猜后半部分的中间点数字。

2. 如何优雅的处理边界条件？

当然是用jiangly同款二分啦，具体看链接二分查找为什么总是写错？_哔哩哔哩_bilibili

3.时间复杂度：O(logn)

【实现】

【例题】

1.丢瓶盖 - 计蒜客 T1878 - Virtual Judge (csgrandeur.cn)（最大值最小化）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 int n,m,a[N];
 5 bool judge(int x)
 6 {
 7     int i,j,sum=0;
 8     for(i=1;i<=n;)
 9     {
10         for(j=i;j<n&&a[j+1]-a[i]<x;j++);
11         i=j+1;
12         sum++;
13     }
14     if(sum>=m) return true;
15     else return false;
16 }
17 int main()
18 {
19     cin>>n>>m;
20     for(int i=1;i<=n;i++) cin>>a[i];
21     sort(a+1,a+n+1);
22     int l=0,r=a[n]-a[1]+1,mid;
23     while(l+1!=r)
24     {
25         mid=l+(r-l)/2;
26         if(judge(mid)) l=mid;
27         else r=mid;
28     }
29     cout<<l<<endl;
30     return 0;
31 }