优化后的代码,样例能过,但是全是WA

P2249 【深基13.例1】查找

bu_chi_suan @ 2024-03-24 17:23:48

#include<stdio.h>

int n,m,a[1000001],b[100001];

void search(int* p1,int q)
{
    int mid,left=0,right=n-1,f=-1;

    while(left<=right)
    {
        mid=left+(right-left)/2;
        if(p1[mid]<q)
        {
            left=mid+1;
        }
        else if(p1[mid]>=q)
        {
            right=mid-1;
        }
    }
    if(p1[mid]==q)
    {
        printf("%d ",mid+1);
        return;
    }
    else
    {
        printf("%d ",-1);
        return;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
     for(int i=0;i<n;i++)
     {
        scanf("%d",&a[i]);
     }
     for(int i=0;i<m;i++)
     {
        scanf("%d",&b[i]);
     }
     for(int i=0;i<m;i++)
     {
        search(a,b[i]);
     }
    return 0;
}

by bu_chi_suan @ 2024-03-24 17:26:26

@bu_chi_suan 下面是80分的代码(最后一个数据超时):

#include<stdio.h>

int n,m,a[1000001],b[100001];

void search(int* p1,int q)
{
    int mid,left=0,right=n-1;

    while(left<=right)
    {
        mid=left+(right-left)/2;
        if(p1[mid]<q)
        {
            left=mid+1;
        }
        else if(p1[mid]>q)
        {
            right=mid-1;
        }
        else
        {
            if(mid==0)
            {
                printf("%d ",mid+1);
                return;
            }
            else
            {
                int t=mid;
                while(1)
                {
                    t--;
                    if(p1[t]!=q)
                    {
                        printf("%d ",t+2);
                        return;
                    }
                }
            }
        }
    }
    printf("%d ",-1);
    return;
}

int main()
{
    scanf("%d%d",&n,&m);
     for(int i=0;i<n;i++)
     {
        scanf("%d",&a[i]);
     }
     for(int i=0;i<m;i++)
     {
        scanf("%d",&b[i]);
     }
     for(int i=0;i<m;i++)
     {
        search(a,b[i]);
     }
    return 0;
}

|