二分边界问题怎么确定
不会， 二分边界问题是指在使用二分查找算法解决问题时，需要确定二分的起始边界和终止边界。通常情况下，起始边界可以是数组或列表的第一个元素的索引，而终止边界可以是数组或列表的最后一个元素的索引。确定边界的方法主要有两种：
1. 根据问题的具体要求：根据问题的特点和限制条件，确定起始边界和终止边界。例如，如果要在一个有序数组中查找某个特定的数值，可以将起始边界设置为0，终止边界设置为数组长度减1。
2. 使用默认边界：对于一些常见的问题，可以使用默认的边界设置。例如，在查找旋转排序数组中的最小值这个问题中，起始边界可以设置为0，终止边界可以设置为数组长度减1。
在确定边界后，通过不断调整边界和计算中间位置来进行二分查找，直到找到目标值或无法再继续划分区域。需要注意的是，边界的选择要保证每次划分都能够缩小待查找的范围，否则可能会导致死循环或找不到目标值的情况发生。因此，在确定边界时要仔细考虑问题的特性和限制条件，确保边界能够正确划分搜索区域。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。 上网搜教程 本帖最后由 柿子饼同学 于 2023-11-23 17:35 编辑
以下是两种模板 , 分别是整数域上的二分 和 实数域上的二分(可以是小数的)
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 是最后答案
页:
[1]