AcWing 789. 把握住循环不变式,你就不会写死循环
原题链接
简单
作者:
suncloud
,
2019-11-04 13:56:22
,
所有人可见
,
阅读 921
#include <iostream>
using namespace std;
const int MAX = 1e5 + 10;
int a[MAX];
int search_last(int n, int k) {
// loop invariant: [L, l] <= k, [r, R] > k
int l = -1, r = n;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] <= k)
l = m;
else
r = m;
}
// l + 1 == r
if (l > -1 && a[l] == k)
return l;
return -1;
}
int search_first(int n, int k) {
// loop invariant: [L, l] < k, [r, R] >= k
int l = -1, r = n;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] < k)
l = m;
else
r = m;
}
// l + 1 == r
if (r < n && a[r] == k)
return r;
return -1;
}
int main() {
int n, q, k;
cin >> n >> q;
for (int i = 0; i < n; ++i) cin >> a[i];
while (q--) {
cin >> k;
cout << search_first(n, k) << ' ' << search_last(n, k) << '\n';
}
return 0;
}