超级爽无脑开区间模板!!!
首先我们要认识到开区间二分的是什么东西,开区间二分的是一条分界线(理解成两个位置之间的一条线!!!),注意一定不要理解成下标!!!
//记住是开区间,假设原区间为[L, R],那么开区间一定满足l < L 和 r > R。
bool check(int x) {...}//满足某种性质的check函数
int binary_search(int x) {
int l = L - 1, r = R + 1;
//因为二分的是一条分界线,所以到结束的时候分界线的左右就是l和r,一定是相差1的
while(l + 1 != r) {
int mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
//下面看情况而定
return l;
//return r;
}
题目分析
根据题目的描述画出左右区间的性质区别
对于第一个二分来说,分为$ >= k$ 和$<k$,因为根据单调性显然是分界线的右边$>=k$,分界线的左边$<k$,所以我们就应该选择分界线的右边,即$a[r]$。
对于第二个二分来说,分为$ > k$和$<=k$,因为根据单调性显然是分界线的右边都$>k$,左边都$<=k$,所以我们就应该选择分界线的左边,即$a[l]$。
#include <iostream>
#define N 100000
using namespace std;
int a[N+50], n, q;
//找到第一个大于等于k的位置
int binary_search1(int k) {
int l = -1, r = n;
while(l + 1 != r) {
int mid = (l + r) / 2;
if(a[mid] >= k) r = mid;
else l = mid;
}
return a[r] == k ? r : -1;
}
//找到第一个大于k的位置
int binary_search2(int k) {
int l = -1, r = n;
while(l + 1 != r) {
int mid = (l + r) / 2;
if(a[mid] > k) r = mid;
else l = mid;
}
return a[l] == k ? l : -1;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> q;
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
for(; q--;) {
int k;
cin >> k;
cout << binary_search1(k) << " " << binary_search2(k) << "\n";
}
return 0;
}