题目描述
blablabla
样例
整数二分的l和r都是while循环的时候不能相等吗?
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> v(n);
for(auto& e : v) cin >> e;
while(m--) {
int x;
cin >> x;
int l = 0, r = n-1;
while(l < r) {
int mid = (l+r)>>1;
if(v[mid] >= x) r = mid;
else l = mid+1;
}
if(v[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(v[mid] <= x) l = mid;
else r = mid-1;
}
cout << l << endl;
}
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla