用c语言实现折半查找

用c语言实现折半查找

#include
int find(int a[],int x,int n,int m)
{int i;
 if(n>m)return -1;
 i=(n+m)/2;
 if(a[i]==x)return i;
 if(a[i]>x)return find(a,x,n,i-1);
 return find(a,x,i+1,m);
}
int main()
{
int a[20]={2,3,6,7,12,18,19,21,25,28,30,33,37,39,42,45,47,49,50,51};
int x,i;

printf("已有的数是：
");for(i=0;i<20;i++)
printf("%d ",a[i]);

printf("
请输入要查找的数：");scanf("%d",&x);
if((i=find(a,x,0,19))>=0)

printf("%d是第%d个数
",x,i+1);

else printf("未找到%d
",x); return 0;

}

int binary_search(int * data,int len,int target)
{
int b;
if (len==1&&*data!=target)b=-1;
else if (target<data[(len)/2]) b=binary_search(data,len/2,target);
else if (target>data[(len)/2]) {
b=binary_search(data+(len/2),len/2+1,target) ;
b+=b==-1?0:len/2;
}
else if (target==data[(len)/2]) b=(len)/2+1;
return b;
}
////////////////////////////////////////////////////////////////
调用示例:
////////////////////////////////////////////////////////////////
//---------------------------------------------------------------------------
#include <stdio.h>
int binary_search(int * data,int len,int target)
{
int b;
if (len==1&&*data!=target)b=-1;
else if (target<data[(len)/2]) b=binary_search(data,len/2,target);
else if (target>data[(len)/2]) {
b=binary_search(data+(len/2),len/2+1,target) ;
b+=b==-1?0:len/2;
}
else if (target==data[(len)/2]) b=(len)/2+1;
return b;
}
int main(void)
{
int a[]={1,3,5,6,7,9,16};
printf("%d\n%d\n",binary_search(a,7,9),binary_search(a,7,15));
return 0;
}
//---------------------------------------------------------------------------

#include<stdio.h>
int binary_search(int * data,int len,int target)
{
int high=len-1,low=0,mid;
mid=(high+low)/2;
while(high>low)
{
if(target>data[mid])
low=mid+1;
else if(target<data[mid])
high=mid-1;
else return mid;
mid=(high+low)/2;
}
return -1;
}
int main()
{
int a[]={0,1,2,3,4,5,6,7,8,9};
int i=binary_search(a,10,5);
if(i==-1)
printf("Not Foun!\n");
else
printf("Foun %d at %d\n",a[i],i);
return 0;
}