欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分答案模板

程序员文章站 2024-03-17 17:14:52
...
#include <iostream>
using namespace std;
int a[] = {1, 2, 4, 5, 7, 8};
//返回最后一个小于k的数的下标
int find1(int k) {
    int l = 0, r = 5;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(a[mid] < k) l = mid;
        else r = mid - 1;
    }
    return l;
}
//返回最后一个小于等于k的数的下标
int find2(int k) {
    int l = 0, r = 5;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(a[mid] <= k) l = mid;
        else r = mid - 1;
    }
    return l;
}
//返回第一个大于k的数的下标
int find3(int k) {
    int l = 0, r = 5;
    while(l < r) {
        int mid = l + r >> 1;
        if(a[mid] > k) r = mid;
        else l = mid + 1;
    }
    return l;
}
//返回第一个大于等于k的数的下标
int find4(int k) {
    int l = 0, r = 5;
    while(l < r) {
        int mid = l + r >> 1;
        if(a[mid] >= k) r = mid;
        else l = mid + 1;
    }
    return l;
}
int main() {
    cout<<find1(5)<<endl; //输出2
    cout<<find2(5)<<endl; //输出3
    cout<<find3(5)<<endl; //输出4
    cout<<find4(5)<<endl; //输出3
    return 0;
}

总结:

  1. 若区间 [l, r] 分成左右两个区间,左区间满足条件,右区间不满足条件,答案是左区间的右端点,则 l = mid,且 mid = (l + r + 1) / 2
  2. 若区间 [l, r] 分成左右两个区间,右区间满足条件,左区间不满足条件,答案是右区间的左端点,则 r = mid,且 mid = (l + r) / 2
相关标签: # 二分/前缀和