跳转至

二分

约 55 个字 100 行代码 预计阅读时间 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;//返回夹出来的位置
    // 也可以返回r, 结束条件为l = r
}

非严格单调序列中找满足条件的最大下标

while (left <= right) {
    int mid = (left + right) / 2;
    if (nums[mid] < nums[i] + nums[j]) {
        k = mid;
        left = mid + 1;   // 往右找更大的满足条件的下标
    } else {
        right = mid - 1;  // 不满足就往左缩
    }
}

模板

// 1. 是否存在 x
int binarySearch(vector<int>& A, int x) {
    int l = 0, r = A.size()-1;
    while (l <= r) {
        int mid = (l+r)/2;
        if (A[mid] == x) return mid;
        else if (A[mid] < x) l = mid+1;
        else r = mid-1;
    }
    return -1;
}

// 2. 第一个 >= x
int lowerBound(vector<int>& A, int x) {
    int l = 0, r = A.size()-1, ans = -1;
    while (l <= r) {
        int mid = (l+r)/2;
        if (A[mid] >= x) { ans = mid; r = mid-1; }
        else l = mid+1;
    }
    return ans;
}

// 3. 最后一个 <= x
int lastLE(vector<int>& A, int x) {
    int l = 0, r = A.size()-1, ans = -1;
    while (l <= r) {
        int mid = (l+r)/2;
        if (A[mid] <= x) { ans = mid; l = mid+1; }
        else r = mid-1;
    }
    return ans;
}
// 如果想找满足==x的最后一个，是不是就是找 < x + 1的最后一个

颜色主题调整

评论区~

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