题解
【入门】二分查找左侧边界
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 r = mid - 1;//以右边界左移 } else{ l = mid + 1; } } if (a[l] == x) {//找到了第一个x出现的位置 cout << l << ' '; } 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-l)/2; if(x<=a[mid]){//加等号让一样的数一直往左 r=mid-1;//向左边更新右边界 }else{ l=mid+1; } } if(a[l]==x){//找到最左边的数 cout<<l<<" "; }else{ cout<<-1<<" "; } } return 0; } -
0
#include<bits/stdc++.h> using namespace std; int n,q,x; int a[100010]; int main(){ cin>>n; for(int i=1; i<=n;i++) cin>>a[i]; cin>>q; for(int i=1;i<=q;i++){ cin>>x; int l=1, r=n, mid; while(l<=r){ mid =(r+l)/2; if(x<=a[mid]) r=mid-1; else l=mid+1; } if(a[l]==x) cout<<l<<" "; else cout<<-1<<" "; } return 0; }
- 1