[已解决]二分边界问题怎么确定

lsmCC

不会，

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2023-11-23 17:30:51

以下是两种模板 , 分别是整数域上的二分 和 实数域上的二分(可以是小数的)
Check(x) 代表 x 作为答案满不满足条件 , 是 1 就满足 , 0 就不满足 , 根据实际需要编写
整数的二分 :

// L, R 是自己设的 最小/最大值
int l = L, r = R, mid, res;

while(l <= r){
        mid = (l + r) / 2;
        // 这个方法是求最大的符合条件的值, l 在增大
        if(Check(mid)) l = mid + 1, res = mid; 
        else r = mid - 1;
        // 求出最小的符合条件的, 看 r 每次在缩小
        // if(Check(mid)) r = mid - 1, res = mid;  
        // else l = mid + 1;
        
        // 两种情况自己看着用
}
// 过后 res 就是答案

实数上二分

double l = L, r = R, mid, res;
double eps = 1e-12;  // 极小值, 如果 r - l < eps 就可以看作相等, eps的设置要根据需要, eps 越小答案精度越高

while(r - l > eps){
        mid = (l + r) / 2;
        // 求最大的符合条件的答案
        if(Check(mid)) l = mid, res = mid;
        else r = mid;
        // 求最小的符合的答案
        // if(Check(mid)) r = mid, res = mid;
        //else l = mid;
}
// res 就是最后的答案

也可以指定循环次数 , 不用 eps , 循环次数自己调 , 次数越多精度越高

int l = L, r = R, mid, res;
for(int i = 0; i < 50; i++){
        mid = (l + r) / 2;
        if(Check(mid)) r = mid, res = mid;
        else l = mid;
        // 另一种情况不用我说了吧
}
// res 是最后答案

跳转到最佳答案楼层

FishC_GPT

二分边界问题是指在使用二分查找算法解决问题时，需要确定二分的起始边界和终止边界。通常情况下，起始边界可以是数组或列表的第一个元素的索引，而终止边界可以是数组或列表的最后一个元素的索引。

确定边界的方法主要有两种：
1. 根据问题的具体要求：根据问题的特点和限制条件，确定起始边界和终止边界。例如，如果要在一个有序数组中查找某个特定的数值，可以将起始边界设置为0，终止边界设置为数组长度减1。
2. 使用默认边界：对于一些常见的问题，可以使用默认的边界设置。例如，在查找旋转排序数组中的最小值这个问题中，起始边界可以设置为0，终止边界可以设置为数组长度减1。

在确定边界后，通过不断调整边界和计算中间位置来进行二分查找，直到找到目标值或无法再继续划分区域。需要注意的是，边界的选择要保证每次划分都能够缩小待查找的范围，否则可能会导致死循环或找不到目标值的情况发生。因此，在确定边界时要仔细考虑问题的特性和限制条件，确保边界能够正确划分搜索区域。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

tommyyu

上网搜教程

柿子饼同学

以下是两种模板 , 分别是整数域上的二分 和 实数域上的二分(可以是小数的)
Check(x) 代表 x 作为答案满不满足条件 , 是 1 就满足 , 0 就不满足 , 根据实际需要编写
整数的二分 :

// L, R 是自己设的 最小/最大值
int l = L, r = R, mid, res;

while(l <= r){
        mid = (l + r) / 2;
        // 这个方法是求最大的符合条件的值, l 在增大
        if(Check(mid)) l = mid + 1, res = mid; 
        else r = mid - 1;
        // 求出最小的符合条件的, 看 r 每次在缩小
        // if(Check(mid)) r = mid - 1, res = mid;  
        // else l = mid + 1;
        
        // 两种情况自己看着用
}
// 过后 res 就是答案

实数上二分

double l = L, r = R, mid, res;
double eps = 1e-12;  // 极小值, 如果 r - l < eps 就可以看作相等, eps的设置要根据需要, eps 越小答案精度越高

while(r - l > eps){
        mid = (l + r) / 2;
        // 求最大的符合条件的答案
        if(Check(mid)) l = mid, res = mid;
        else r = mid;
        // 求最小的符合的答案
        // if(Check(mid)) r = mid, res = mid;
        //else l = mid;
}
// res 就是最后的答案

也可以指定循环次数 , 不用 eps , 循环次数自己调 , 次数越多精度越高

int l = L, r = R, mid, res;
for(int i = 0; i < 50; i++){
        mid = (l + r) / 2;
        if(Check(mid)) r = mid, res = mid;
        else l = mid;
        // 另一种情况不用我说了吧
}
// res 是最后答案