二分查找左边界求调教~~

P2249 【深基13.例1】查找

IKUN_LMX @ 2023-07-13 15:27:24

题目:

(https://www.luogu.com.cn/problem/P2249)


#include<bits/stdc++.h>
using namespace std;
const int  N=10100;int n,q;
int b[N];   
int c[100000001],a[100000001];
int main(){
    scanf("%d",&n);scanf("%d",&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=1;i<=q;i++){
        scanf("%d",&b[i]);  
    }
    int sum=1;
    int r=n,l=1,mid;
    while(l<=r){

    mid=(l+r)/2;         
    if(a[mid]==b[sum]){
    r=mid-1;
    }
    if(a[mid]>b[sum]){
    r=mid-1;
    }
    if(a[mid]<b[sum]){
    l=mid+1;
    }
    if(a[l]==b[sum]){

    c[sum]=l;
    sum++;
    r=n,l=1;
    }
}
for(int i=1;i<=q;i++){
    if(c[i]!=0){
        printf("%d ",c[i]);
    }
    else{
    printf("%d ",-1);
    }
}
    return 0;
}      

by Gohidg @ 2023-07-13 19:13:39

@Lmx091214

int bin(int x){//查找首位置
    int l=1,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(arr[mid]==x){
            ans=mid;
            r=mid-1;
        }else if(arr[mid]>x){
            r=mid-1;
        }else if(arr[mid]<x){
            l=mid+1;
        }
    }
    if(ans==0)return -1;
    return ans;
}

arr为查找数组


|