[//]: # 二分查找实际上是,查找>=x或<=x的集合x边界。
可以把查找过程先以x为中心写出来。最后通过画图判断,是找左边界还是右边界。
题目描述
blablabla
样例
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], n, q;
int find_l(int x)
{
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(x > a[mid]) l = mid + 1;
else r = mid;
}
if(x != a[l]) return -1;
return l;
}
int find_r(int x)
{
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(x < a[mid]) r = mid - 1;
else l = mid;
}
if(x != a[l]) return -1;
return l;
}
int main()
{
cin >> n >> q;
for(int i = 0; i < n; i++) cin >> a[i];
while(q --)
{
int k;
cin >> k;
int l = find_l(k), r = find_r(k);
cout << l << ' ' << r << endl;
}
return 0;
}
算法1
$O(logn)$
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla