二分模板 个人比较喜欢 这样每次端点值都改变 方便记忆
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
int ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid)) { // check()判断mid是否满足性质
r = mid - 1;
ans = mid;
};
else l = mid + 1;
}
return ans;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
int ans = 0;
while (l <= r)
{
int mid = l + r + 1 >> 1;
if (check(mid)){
l = mid + 1
ans = mid;
}
else r = mid - 1;
}
return ans;
}
本题题解
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
while (m -- )
{
int x;
scanf("%d", &x);
int l = 0, r = n - 1,ans = 0;
while (l <= r)
{
long long mid=(l+r)/2;
if (q[mid] >= x)
{
r = mid - 1;
ans = mid;
}
else
l=mid + 1;
}
if (q[ans] != x) cout << "-1 -1" << endl;
else
{
cout << ans << ' ';
int l = 0, r = n - 1, ans;
while (l <= r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x) {
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
cout << ans << endl;
}
}
return 0;
}
yxc模板代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
while (m -- )
{
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
if (q[l] != x) cout << "-1 -1" << endl;
else
{
cout << l << ' ';
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
ool check(int x)
,应该是bool
吧对 我又改了一下