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

lsmCC

不会，

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2023-11-23 17:30:51

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

1. // L, R 是自己设的 最小/最大值
   
2. int l = L, r = R, mid, res;
   
3. 
   
4. while(l <= r){
   
5.         mid = (l + r) / 2;
   
6.         // 这个方法是求最大的符合条件的值, l 在增大
   
7.         if(Check(mid)) l = mid + 1, res = mid;
   
8.         else r = mid - 1;
   
9.         // 求出最小的符合条件的, 看 r 每次在缩小
   
10.         // if(Check(mid)) r = mid - 1, res = mid;  
    
11.         // else l = mid + 1;
    
12.        
    
13.         // 两种情况自己看着用
    
14. }
    
15. // 过后 res 就是答案

复制代码

实数上二分

1. double l = L, r = R, mid, res;
   
2. double eps = 1e-12;  // 极小值, 如果 r - l < eps 就可以看作相等, eps的设置要根据需要, eps 越小答案精度越高
   
3. 
   
4. while(r - l > eps){
   
5.         mid = (l + r) / 2;
   
6.         // 求最大的符合条件的答案
   
7.         if(Check(mid)) l = mid, res = mid;
   
8.         else r = mid;
   
9.         // 求最小的符合的答案
   
10.         // if(Check(mid)) r = mid, res = mid;
    
11.         //else l = mid;
    
12. }
    
13. // res 就是最后的答案

复制代码

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

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

复制代码

跳转到最佳答案楼层

FishC_GPT

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

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

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

tommyyu

上网搜教程

柿子饼同学

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

1. // L, R 是自己设的 最小/最大值
   
2. int l = L, r = R, mid, res;
   
3. 
   
4. while(l <= r){
   
5.         mid = (l + r) / 2;
   
6.         // 这个方法是求最大的符合条件的值, l 在增大
   
7.         if(Check(mid)) l = mid + 1, res = mid;
   
8.         else r = mid - 1;
   
9.         // 求出最小的符合条件的, 看 r 每次在缩小
   
10.         // if(Check(mid)) r = mid - 1, res = mid;  
    
11.         // else l = mid + 1;
    
12.        
    
13.         // 两种情况自己看着用
    
14. }
    
15. // 过后 res 就是答案

复制代码

实数上二分

1. double l = L, r = R, mid, res;
   
2. double eps = 1e-12;  // 极小值, 如果 r - l < eps 就可以看作相等, eps的设置要根据需要, eps 越小答案精度越高
   
3. 
   
4. while(r - l > eps){
   
5.         mid = (l + r) / 2;
   
6.         // 求最大的符合条件的答案
   
7.         if(Check(mid)) l = mid, res = mid;
   
8.         else r = mid;
   
9.         // 求最小的符合的答案
   
10.         // if(Check(mid)) r = mid, res = mid;
    
11.         //else l = mid;
    
12. }
    
13. // res 就是最后的答案

复制代码

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

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

复制代码