top1编程
← 返回题目
题解

【入门】二分查找右侧边界

3 条题解

  • 0
    @ 2026-7-29 20:22:04
    #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 << &#39; &#39;; 
    		} else {
    			cout << -1 << &#39; &#39;;
    		}
    	}
    	return 0;
    }
    
    • 0
      @ 2026-7-29 0:06:25
      #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
        @ 2026-7-28 22:10:01
        #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