二分常见模型

二分法常见模型

  • 二分查找(基础)
  • 二分答案(重点)
  • 代替三分(*)

注:*为扩展内容

二分答案概念

二分答案,就是二分枚举答案,由于进行二分,所以时间复杂度 O(二分次
数*单次判定时间复杂度)。

二分答案与二分查找类似,即对有着单调性的答案进行二分,确定可能的答案后,配合贪心、
DP 等其他算法检验这个答案是否合理,不断缩减范围,最终确定答案的方法。常见的检验
算法如穷举、贪心、搜索、动态规划、图论、数据结构等,可以看到,二分答案问题很好地
结合了其他算法知识,非常受命题者欢迎。
pic.jpg
答案的单调性大多数情况下可以转化为一个函数,其单调性证明多种多样,如下:

可以解决的常见问题

代码框架

为了保证解在二分搜索的区间里,故不同的问题有着不同(但相似)的写法,可以自己画一
个区间模拟一下。

整数定义域上的万能二分(★推荐)

int binary()
{
    int l =/*答案下限*/, r =/*答案上限*/, ans = 0;
    while(l <= r)
{
    int mid = (l + r) / 2;  // 防溢出, 根据数据大小调整,   mid = l+(r-l)/2
if(check(mid)) ans = mid, l = mid + 1;  // 根据具体题意,缩小范围
else r = mid - 1;
}
return ans;
}

求最小值

int binary()
{
int l =/*答案下限*/, r =/*答案上限*/, mid;
while(l < r)
{
    mid = (l + r) / 2;
    if(check(mid)) r = mid;
    else l = mid + 1;
}
return r;
}

求最大值

int binary()
{
int l =/*答案下限*/, r =/*答案上限*/, mid;
while(l < r)
{
    mid = (l + r + 1) /2;
    if(check(mid)) l = mid;
    else r = mid - 1;
}
return l;
}

实数定义域上的二分

double binary()
{

//为了防止死循环,因为当 l+1=r 时刚好符合条件,
// (l+r)/2=l,就会无限循环。

double l =/*答案下限*/, r =/*答案上限*/;
while(fabs(l-r) > dlt)   // dlt=1e-6 具体精度根据题目要求决定
{
    double mid = (l + r) / 2;
    if(check(mid)) r=mid;
    else l = mid;
}
return r;// 根据具体题意,缩小范围
}

由于实数运算带来的精度问题,若 dlt 取太小就会导致程序死循环,因此往往指定二分次数更好。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
下一篇