若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

2413: C语言习题 折半查找

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 2,019

题目描述

有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

参考代码

#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("1n");
        result=searchfor (a,n,m);
        printf("%dn",result);
        //printf("1n");
    }
    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;
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 原站点 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist