题目描述
小C同学有n个苹果,每个苹果的甜度都不相同,他现在想要吃一个甜度为a的苹果,可他又不想一个个去找,聪明的你能帮他在最少次数(相对次数最少)内找出甜度为a的苹果吗。
输入
第一行输入苹果的个数n(0<n<300000)
下面n行从小到大输入苹果的甜度。(保证没有重复)
第n+2行,输入需要找的苹果的甜度
输出
若找到,输出你寻找的次数。否则,输出"I can't find it."
样例输入
5
1
2
3
4
5
2
样例输出
3
参考代码
#include<stdio.h>
int hanshu(int n, int v);
int a[300010];
int main()
{
int n,i,m;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
hanshu(n,m);
return 0;
}
int hanshu(int n, int v)
{
int top=n-1,bot=0,c=0,i,mid;
while(top>=bot)
{
mid=(top+bot)/2;
if(v==a[mid])
{
c++;
break;
}
if(v>a[mid])
bot=mid+1;
if(v<a[mid])
top=mid-1;
c++;
}
int k=0;
for (i=0;i<n;i++)
{
if(v==a[i])
{
k=1;
break;
}
}
if(k==1)
printf("%dn",c);
if(k==0)
printf("I can't find it.");
return 0;
}
解析
暂无