80分求调

P2249 【深基13.例1】查找

xiesichen666 @ 2024-11-04 17:30:11

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
const int N=1000000+1;
int a[N];
int l,r,mid=0,n,gs,mc;
void find(int k,int l,int r){
    while(l<r){
        mid=(l+r)/2;
        if(a[mid]==k&&a[mid-1]!=k){
            printf("%d ",mid);
            return;
        }else{
            if(a[mid]>k){
                r=--mid;
            }else{
                if(a[mid-1]==k){
                    r--;
                }else{
                    l=mid+1;                
                }
            }
        }
    }
    if(a[l]!=k){
        printf("-1 ");
    }else{
        printf("%d ",l);
    }
}
int main(){
    scanf("%d%d",&n,&gs);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=gs;i++){
        l=1;
        r=n;
        scanf("%d",&mc);
        find(mc,l,r);
    }
    return 0;
}

80分，最后一个点TLE，求调！！！！！！！！！

by Lyd1107 @ 2024-11-07 16:45:06

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m;
int a[N];

int find(int x) {
    int l = 1, r = n;
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[mid] == x) {
            ans = mid;
            r = mid - 1;
        } else if (a[mid] > x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return ans;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    while (m--) {
        int q;
        scanf("%d", &q);
        printf("%d ", find(q));
    }
    return 0;
}