Question

帮忙编一道C语言题

请编写函数int fun(double a[ ], int k, int m, double x)，它的功能是：用递归方法在数组a中查找x是否出现，其中数组a的元素已按由大到小的次序排序，k和m是数组的最小和最大下标，函数采用二分查找算法，若找到则返回1，否则返回0。

谢谢。。

Answer 1

int fun(double a[],int k,int m,double x)
{
int mid;
mid=(k+m)/2;
if(k>=m)
return 0;

else if(x==a[mid])
return 1;
else
{
return fun(a,k,mid,x)+fun(a,mid+1,m,x);
}
}

测试程序：
main()
{
double aa[10]={1,2,3,4,5,6,7,8,9,0},x;
printf("%d\n%d\n",fun(aa,0,9,8),fun(aa,0,9,99));

}
输出为：
1
0

Answer 2

#include <stdio.h>
int fun(double a[ ], int k, int m, double x)
{
if(k>=m)
return 0;
if(a[(k+m)/2+1] > x)
{
m = (k+m)/2+1;
}
else if(a[(k+m)/2+1] < x)
{
k = (k+m)/2 + 1;
}
else
return 1;
fun(a,k,m,x);
}

Answer 3

int fun(double a[],int k,int m,double x){
if(k==m){
if(a[k]==x) return 1;
else return 0;
}
else{
int i=(k+m)/2;
if(a[i]==x) return 1;
else if(a[i]<x) return fun(a,k,i-1,x);
else if(a[i]>x) return fun(a,i+1,m,x);
}
}

Answer 4

int fun(double a[],int k,int m,double x)
{
if ( a[k + (m - k)/2 - (m - k + 1)%2] == x)
{
return 1;
}
else if ( a[k + (m - k)/2 - (m - k + 1)%2] > x )
{
fun(a,k + (m - k)/2 - (m - k + 1)%2,m,x);
}
else if ( a[k + (m - k)/2 - (m - k + 1)%2] < x)
{
fun(a,k,k + (m - k)/2 - (m - k + 1)%2,x);
}
return 0;
}