题目描述
blablabla
include [HTML_REMOVED]
using namespace std;
const int N = 1e5 + 10;
int q[N],s[N];
int n,m;
int find_1(int x)
{
int l = 0, r = n - 1; //q【mid】符合题意的在右边,所以满足条件的时候r=mid,从右向左缩小区间
while(l < r) { // 不满足的时候,说明满足条件的在mid右边,区间缩小为l=mid+1
int mid = l + r >> 1;
if(s[mid] >= x) r = mid;
else l = mid + 1;
}
if(s[l] == x) return l;
return -1;
}
int find_2(int x)
{
int l = 0,r = n - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(s[mid] <= x) l = mid;
else r = mid - 1;
}
if(s[l] == x) return l;
return -1;
}
int main()
{
cin>>n>>m;
for(int i = 0; i < n; i) cin>>s[i];
for(int i = 0; i < m; i) cin>>q[i];
for(int i = 0; i < m; i++) {
if(find_1(q[i]) != -1) cout<<find_1(q[i]);
else cout<<-1;
cout<<” “;
if(find_2(q[i]) != -1) cout<<find_2(q[i]);
else cout<<-1;
cout<<endl;
}
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla