题目描述
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
解题报告
题意理解
在一个范围内,查找一个数字,要求找到这个元素的起始位置和结束位置,请注意这个范围内的数字都是单调递增的,即具有单调性质.
算法理解
一个题目,如果一个区间具有单调性质,那么一定可以二分,但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分.
——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;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39787/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
蒟蒻代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,a[N];
void Up(int x)
{
int l=0,r=n-1;
while (l<r)
{
int mid=l+r>>1;
if (a[mid]>=x)
r=mid;
else
l=mid+1;
}
if (a[l]!=x)
l=-1;
cout<<l<<' ';
return;
}
void Down(int x)
{
int l=0,r=n-1;
while (l<r)
{
int mid =l+r+1>>1;
if (a[mid]<=x)
l=mid;
else
r=mid-1;
}
if (a[l]!=x)
l=-1;
cout<<l<<endl;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>q;
for (int i=0; i<n; i++)
cin>>a[i];
while (q--)
{
int x;
cin>>x;
Up(x);
Down(x);
}
return 0;
}
//逆乾大佬代码,我康康后觉得超好理解啊!
阅读博客密码:Acwinghh 各位不要外传哦,毕竟大家都是VIP大佬!
https://blog.csdn.net/WJPnb1/article/details/126360962?spm=1001.2014.3001.5502
这篇blog写的好，不用考虑mid-1和mid+1的边界问题
可以可以
找最左边的那个元素，为什么是l就是你所找的位置呢，不是r吗。只有 a[r]才有可能＝a[mid]，只有判断这两个值是否相等了，缩短右边界，r＝mid刚好排除右边。这个时候左边就都不满足条件了
什么是更好的阅读体验？
#include <iostream> using namespace std; const int N = 1e5 + 5; int main() { int n, q, data[N]; cin >> n >> q; for (int i = 0; i < n; i++) cin >> data[i]; while (q--) { int k; cin >> k; // 寻找第一个等于 k 的坐标 int left = -1, right = n; while (left + 1 != right) { int mid = (left + right) >> 1; if (data[mid] >= k) right = mid; else left = mid; } // 循环结束后，right即为第一个大于等于 k 的下标 if (data[right] != k) cout << "-1 -1" << endl; else { cout << right << " "; // 找最后一个 k 的位置 left = -1, right = n; while(left + 1 != right) { int mid = (left + right) >> 1; if (data[mid] <= k) left = mid; else right = mid; } // 可以直接输出，不需要判断 if (data[left] != k), 因为else已经保证至少存在一个k cout << left << endl; } } system("pause"); return 0; }这样不行吗头大
#include[HTML_REMOVED]
using namespace std;
const int N=100010;
int n,q;
int arr[N];
int binary_search1(int arr[],int len,int x){
int l=-1,r=len;
while(l+1<r){
int mid=(l+r)/2;
if(arr[mid]<x)
l=mid;
else r=mid;
}
if(arr[r]==x) return r;
else return -1;
}
int binary_search2(int arr[],int len,int x){
int l=-1,r=len;
while(l+1<r){
int mid=(l+r)/2;
if(arr[mid]<=x){
l=mid;
}
else r=mid;
} if(arr[l]==x) return l; else return -1;}
int main(){
cin>>n>>q;
for(int i=0;i[HTML_REMOVED]>arr[i];
}
while(q–){
int x;
cin>>x;
int res1=binary_search1(arr,n,x);
if(res1==-1){
cout<<”-1 -1”<<endl;
continue;
}
int res2=binary_search2(arr,n,x);
cout<<res1<<” “<<res2<<endl;
}
return 0;
}
第一句是头文件他显示错了，大家伙帮我康康为什么这个在洛谷不行
所谓的二分算法,就是我们知道当前的候选区间中,一定存在我们要找到的答案,而且我们发现这个区间拥有单调性质此类的性质,那么我们可以不停地缩减候选区间的范围,达到排除无用答案的效果.
这段话很准确
想问一下为什么找左边界的时候用的条件是
···
if (q[mid] >= x) r = mid;
else l = mid + 1;
···
用小于不可以吗
小于的话不就是调换了一下if和else的内容吗（？
因为当q[mid]满足条件的时候，假设要找的数是x，那么q[mid[]肯定在数x的右边或者正好就是x，因为x右边的数都会比x大或者等于x， 所以答案是在mid的左边，但是包括mid，所以就是把r变成mid，即区间从l到mid 一定要记住数列是有序的
“但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分”这句话不是能很好地理解 ，可以解释一下吗%%%
二分的是指将答案二分，和单调性没有关系，将所有结果列举出来，然后寻找符合题意的结果，在寻找过程中用的是二分，跟单调没有关系，然后单调不是二分的必要条件，只有二分查找需要单调性。
emmm，我好好理解下，谢谢大佬
不敢不敢，我还是个小菜鸟，昨天刚刚看了二分，
orz
大佬，第二个模板中main里头的第一句是啥意思啊？
y总代码：
while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] <= x) l = mid; else r = mid - 1; }是不是可以改成
while(a[l]==k) l++;然后再输出l-1;
第一个模板 不需要第二次为 l 赋值了吧
这个 @yxc吧.
不需要啦