题解
【入门】二分查找右侧边界
3 条题解
-
0
#include <bits/stdc++.h> using namespace std; int a[100005], n, x, mid, q; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } cin >> q;//要查找的数的个数 while (q--) { cin >> x; int l = 1, r = n; while (l <= r) { mid = (l + r) / 2;//计算中间下标 if (a[mid] <= x) {//当前查找到的值小于等于x l = mid + 1; } else{ r = mid - 1; } } if (a[r] == x) {//找到了x右侧出现的位置 cout << r << ' '; } else { cout << -1 << ' '; } } return 0; } -
0
#include <bits/stdc++.h> using namespace std; int a[100005]; int main() { int n,q,x; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cin>>q; while(q--){ cin>>x; int l=1,r=n,mid; while(l<=r){ mid=(l+r)/2; if(x>=a[mid]){//一样的数一直往右 l=mid+1;//向右边更新左边界 }else{ r=mid-1; } } if(a[r]==x){//找到最左边的数 cout<<r<<" "; }else{ cout<<-1<<" "; } } return 0; } -
0
#include <bits/stdc++.h> using namespace std; int a[100005],n,q,x; int f(int x){ int l=1,r=n,mid; while(l<=r){ mid=(l+r)/2; if(a[mid]<=x){ l=mid+1; }else if(a[mid]>x){ r=mid-1; } } if(a[l-1]==x){ return l-1; }else{ return -1; } } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cin>>q; while(q--){ cin>>x; cout<<f(x)<<" "; } return 0; }
- 1