二分

约 58 个字 71 行代码 预计阅读时间 1 分钟

[参考文章]：https://blog.csdn.net/yaoyaoxuanxuan1/article/details/129110080?ops_request_misc=&request_id=&biz_id=102&utm_term=%E4%BA%8C%E5%88%86%E4%B8%87%E8%83%BD%E5%86%99%E6%B3%95&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-129110080.nonecase&spm=1018.2226.3001.4187

严格单调序列中查找值x的位置

//在[A,B]区间内查找x的位置，若不存在则返回-1
int search(int A,int B,int x)
{
    while(A<=B)
    {
        //取中间位置为本轮的猜测值
        int mid = (A+B)/2;
        if(mid==x) {
            return mid;
        }
        else if(mid<x){
            A=mid+1;
        }else{
            B=mid-1;
        }
    }
    return -1;
}

非严格单调序列中第一个大于等于x的位置

int lower_bound(int l,int r,int x)
{
    int mid;//mid为l和r的中点
    int answer = -1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(A[mid]>=x){//中间的数大于等于x
            answer = mid;
            r = mid;//往左子区间[l,mid]中继续找
        }else{
            l = mid + 1;//往右子区间[mid+1,r]中找
        }
        if(l==r)break;
    }
    return answer;//返回夹出来的位置
}







int lower_bound(int l,int r,int x)
{
    int mid;//mid为l和r的中点
    while(l<r)
    {
        mid=(l+r)/2;
        if(A[mid]>=x){//中间的数大于等于x
            r = mid;//往左子区间[l,mid]中继续找
        }else{
            l = mid + 1;//往右子区间[mid+1,r]中找
        }
    }
    return l;//返回夹出来的位置
}

// 待考察

非严格单调序列中最后一个小于等于x的位置

int l = 0;
int r = n - 1;
while(l < r){
    int mid = l + r + 1 >> 1; //注意这边要加1
    if(nums[mid] <= x){
        l = mid;
    }else{
        r = mid - 1; // 有-1出现所以要+1
    }
}
return l;

颜色主题调整

red pink purple indigo blue cyan teal green lime orange brown grey black white

评论区~

有用的话请给我个赞和 star =>
快来跟我聊天~