C语言习题 折半查找

C语言习题 折半查找

时间: 1ms        内存:128M

描述:

有n个数(n<=1000000),这n个数已按从大到小顺序存放在一个数组中,然后有T次查询,每次输入一个数,要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出0。

输入:

第一行数组元素的个数n

第二行n个数组元素的值
第三行输入查询次数T (T<=100000)

往下有T行,每行输入一个需要查询的数字

输出:

查找的值在数组中的位置

示例输入:

10
10 9 8 7 6 5 4 3 2 1
2
9
5

示例输出:

2
6

提示:

参考答案(内存最优[4900]):

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,t,l,h,k,j,i;
    scanf("%d",&n);
    int x[n];
    for(i=0;i<n;i++)
        scanf("%d",&x[i]);
    scanf("%d",&t);

    for(i=0;i<t;i++)
    {
        scanf("%d",&k);
           l=0;
    h=n-1;
        while(l!=h)
        {
            if(x[(l+h)/2]<=k)
                h=(l+h)/2;
            else
                l=(l+h)/2+1;
        }
        if(k==x[h])

            printf("%d\n",h+1);
        else
            printf("0\n");

    }
    return 0;
}

参考答案(时间最优[181]):

#include<stdio.h>
int a[1000001];
int main()
{
    int i,j,n,T,m,result=0;
    int searchfor(int a[],int n,int m);
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&m);
        //printf("1\n");
        result=searchfor(a,n,m);
        printf("%d\n",result);
        //printf("1\n");
    }
    return 0;
}
int searchfor(int a[],int n,int m)
{
    int low,height,i,j,mid;
    low=0,height=n-1;
    int mina=99999999;
    int flag=0;
    while(low<=height)
    {
        mid=(height+low)/2;
        if(a[mid]==m){
            if(mina>mid)
            {
                mina=mid;
            }
            height=mid-1;
            flag=1;
        }
        if(a[mid]<m)
        {
            height=mid-1;
        }
        if(a[mid]>m)
        {
            low=mid+1;
        }
    }
    if(flag==0)
        mina=0;
    else
        mina+=1;
    return mina;

}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注