7-1 二分查找
分数 20
作者 陈晓梅
单位 广东外语外贸大学
输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入格式:
输入共三行：
第一行是n值；
第二行是n个整数；
第三行是x值。
输出格式:
输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入样例:
4
1 2 3 4
1
输出样例:
0
2
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C (gcc)
1
二分法没问题啊
#include <stdio.h>
int main()
{
int n,i,x,left,right,mid,count=0;
int a[1000];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&x);
left = 0;
right = n-1;
while(left <= right)
{
count++;
mid = (left + right)/2;
if(a[mid] == x)
break;
else if(a[mid] > x)
right = mid - 1;
else
left = mid + 1;
}
if(left > right)
{
printf("-1\n");
printf("%d",count);
}
else
{
printf("%d\n",mid);
printf("%d",count);
}
return 0;
}