题目,给定一个按值有序(升序)的N元整数数组A,采用折半查找法查找关键值k的位置,并给出查找的过程
【输入形式】
第一行:N
第二行:A[0], A[1], ... , A[N-1]
第三行:k
【输出形式】
第一行:k的位置(索引),若不存在则输出'no'
第二行:查找的过程,每一次折半的中间(mid)位置的值,以逗号分隔。例如,1 2 3 4 5的中间位置为3,1 2 3 4的中间位置为2。
【样例输入1】
11
2,5,8,11,15,16,22,24,27,35,50
22
【样例输出1】
6
16,27,22
【样例输入2】
11
2,5,8,11,15,16,22,24,27,35,50
10
【样例输出2】
no
16,8,11
【样例说明】
【评分标准】
必须使用折半法,其他方法不能得分。
#include<stdio.h>
int panduan(int n,int key,int a[]);
int panduan(int n,int key,int a[])
{ int low=0,high=n-1,mid,i=0;
int b[n];
int j=0;
while(low<=high)
{ mid=(low+high)/2;
b[j]=mid;
j++;
if(key==a[mid])i=mid;
else if(key<a[mid])high=mid-1;
else low=mid+1; }
if(a[mid]==key)printf("%d\n",i);
else printf("no\n");
for(i=0;i<j;i++)
{ if(i<j-1)printf("%d,",b[i]);
else printf("%d",b[i]); }
return 0; }
int main(){
int n,i,key;
scanf("%d",&n);
int a[100];
for (i=0;i<n;i++)
{ if(i<n-1)scanf("%d,",&a[i]);
else scanf("%d",&a[i]); }
scanf("%d",&key);
panduan(n,key,a);
return 0; }