判断题 适中
#24794

若数组 a 已按升序排列,则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。 int lowerBound(vector<int>&…

若数组 a 已按升序排列,则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。

int lowerBound(vector<int>& a, int x){
    int l=0, r=a.size();
    while(l < r) {
        int mid = (l + r) / 2;
        if( a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析
初始化左边界 l 为 0,右边界 r 为数组长度,形成左闭右开区间 [l, r)。循环条件为 l < r,确保搜索区间非空。每次取中点 mid = (l + r) / 2,若 a[mid] >= x,则第一个满足条件的位置不会在 mid 右侧,故将 r 更新为 mid;否则位置必定在 mid 右侧,将 l 更新为 mid + 1。循环结束时 l 等于 r,返回 l 即为第一个大于等于 x 的元素位置。代码逻辑基于二分查找的下界变种,维护了“答案在 [l, r) 内”的不变式。