杭州网站的建设,wordpress自定义字段分类,网站空间域名续费,广西南宁生活网对于一个递增序列我们要找大于等于target的数#xff0c;返回结果的下标时 比如 序列 5 7 7 8 8 10 初始化左右指针l0 rn-1 猜测区间 [l,r] 闭区间#xff0c;mid(lr)/2 防溢出就写成 midl(r-l)/2 如果有nums[mid]target 那么[l,mid]这个区间的数就都小于target 更新 lmi…对于一个递增序列我们要找大于等于target的数返回结果的下标时 比如 序列 5 7 7 8 8 10 初始化左右指针l0 rn-1 猜测区间 [l,r] 闭区间mid(lr)/2 防溢出就写成 midl(r-l)/2 如果有nums[mid]target 那么[l,mid]这个区间的数就都小于target 更新 lmid1; 否则就是nums[mid]target [mid,r]这个区间的数都大于等于target 更新rmid-1; 终止时返回l,拿这个案例序列走一遍找8最后l和r都指向下标3处的8,此时,l3,r3,mid3 然后更新rmid-12 lr 跳出循环 结果就是l或 r1 返回3再比如找3会发现r不断更新r1,-1 跳出循环 返回l0, 当找大于10的数时l不断更新r不动了最后跳出循环就是返回数组的长度
int lower_bound1(vectorintnums,int target)
{int l0,rnums.size()-1; //闭区间[l,r]while(lr){int midl(r-l)/2 //防溢出if(nums[mid]target)lmid1;else rmid-1;}return l; //最后跳出循环 lr 结果是r1 或者l 因为 此时r1l
}int lower_bound2(vectorintnums,int target)
{int l0,rnums.size(); // 左闭右开 [l,r)while(lr){int midl(r-l)/2;if(nums[mid]target)lmid1;elserightmid;}return l //或者return r
}int lower_bound3(vectorintnums,int target)
{int l-1,rnums.size() ; // 开区间 (l,r)while(l1r){int midl(r-l)/2;if(nums[mid]target)lmid;elsermid;}return r;
}上述我们讨论了 在序列中找 target 的计算方法 对于target target target 这里都可以从第一种情况来转换 我们要找大于target的数就可以使用上面的lower_bound 找 target1 我们要找小于target的数 就可以使用上面的lower_bound招到target 的数左边的那个数也就是返回的下标再减一 我们找小于等于target的数 就可以使用前面大于target返回的结果减一
