折半查找非遞歸與遞歸實作:
#include<stdio.h>
int linner(int a[],int n,int value);
int halfSearch(int a[],int n,int value);
int halfSearch2(int a[],int n,int value,int left,int right);
void main()
{
int a[8]= {12,34,50,53,123,135,167,189};
// int num=linner(a,8,53);//線性查找
// int num=halfSearch(a,8,167); //非遞歸
int num=halfSearch2(a,8,167,0,7);//遞歸
if(num==-1)
printf("沒有找到這個數");
else
printf("位置在第:%d",num);
}
int linner(int a[],int n,int value) //線性查找
{
for(int i=0; i<n; i++)
if(a[i]==value)
return i+1;
return -1;
}
int halfSearch(int a[],int n,int value)//非遞歸折半查找
{
int left=0,right=n-1,mid;
while(left<=right)
{
mid=(left+right)/2;
if(value>a[mid])
left=mid+1;
else if(value<a[mid])
right=mid-1;
else
return mid+1;
}
return -1;
}
int halfSearch2(int a[],int n,int value,int left,int right) //遞歸折半查找
{
if(left>right)
return -1;
int mid=(left+right)/2;
if(a[mid]==value)
return mid+1;
else if(value>a[mid])
return halfSearch2(a,n,value,mid+1,right);
else
return halfSearch2(a,n,value,left,mid-1);
}