信息学竞赛模板（二）— 二分查找

2021-02-04 · 76次阅读 · 原创 · 数据结构与算法

1 整数形式

while(l < r){
    int mid = l + r >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
}

注：还可以使用库里的 lower_bound 代替。

while(l < r){
    int mid = l + r + 1 >> 1;
    if(check(mid)) l = mid;
    else r = mid - 1;
}

若要求保留 k 为位小数，则将精度设置为 $eps = 10^{-(k+2)}$ 。

while(l + eps < r){		//eps = 10^-(k+2)
    double mid = (l + r) / 2;
    if(check(mid)) r = mid;
    else l = mid;
}

while(l + eps < r){		//eps = 10^-(k+2)
    double mid = (l + r) / 2;
    if(check(mid)) l = mid;
    else r = mid;
}

直接循环100次。

for(int i = 0; i < 100; i ++){
    double mid = (l + r) / 2;
    if(check(mid)) r = mid;
    else l = mid;
}

for(int i = 0; i < 100; i ++){
    double mid = (l + r) / 2;
    if(check(mid)) l = mid;
    else r = mid;
}

标题：	信息学竞赛模板（二）— 二分查找
链接：	https://www.fightingok.cn/detail/42
更新：	2022-09-18 22:33:47
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可