int a[100]= {1,2,3,5,11,12,14,15,29,55}//数组中的数（由小到大）
int k//要找的数字
int found(int x,int y)
{ int m=x+(y-x)/2
if(x>y)//查找完毕没有找到答案，返回-1
return -1
else
{ if(a[m]==k) return m//找到就返回位置.
else if(a[m]>k) return found(x,m-1)//找左边
else return found(m+1,y)//找右边
}
}
int main()
{ scanf("%d",&k)//输入要找的数字
printf("%d\n",found(0,9))//从数组a[0]到a[9]进行查找
return 0
}
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，已知一个有n个元素的有序序列, 将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x, 直到找到x或者是没有找到!如果是常规的方法的话那么我们可以通过循环的方式, 按照上面说的算法, 找到则退出循环, 否则继续循环直到左下标位置小于或者等于右下标的位置.
按兄弟你的意思是要用递归方法进行搜索, 那么大概还是上面的算法, 只是把循环的方式改成递归方式: 如果没找到,则确定新的搜索范围, 即左右下标新位置, 然后把新的参数传给函数继续调用函数进行递归搜索!!
递归方式实现详细代码如下:
#include <stdio.h>
#define ARRAY_SIZE 10
#define NOT_FOUND -1
int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2
if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid
}
else if (NumToSearch <array[mid])
{
right = mid - 1
return BinarySearch(array, left, right, NumToSearch)
}
else
{
left = mid + 1
return BinarySearch(array, left, right, NumToSearch)
}
}
return NOT_FOUND
}
int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222}//假设一个已知的有序且是升序数列
int result = 0//查找的结果
int x = 13//假设我们要查找的数是13
int left = 0//序列开始下标
int right = ARRAY_SIZE - 1//序列结尾下标
result = BinarySearch(a, left, right, x)
if (result == NOT_FOUND)
{
printf("Not Found!\n")
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result)
}
return 0
}
希望对兄弟你有帮助!
你把main()
{
"""""
c[i]=RecorBinarySearch(a[i],i,n,b,low,high,mid)
改成
c[i]=RecorBinarySearch(a,b,0,n-1)
}
然后涵数就改成这样
int RecorBinarySearch(int *a , int b , int n0, int n1)
{ int d=(n0+n1)/2
if (b==a[d]) return d
if (b>a[d])n0=d+1
else n1=d-1
if (n1==n0)
{if (b==a[n0]) return n0
else return -1
}
if (n1<n0)return -1
return (RecorBinarySearch(a, b, n0, n1))
}
这涵数程式我测试过, 应该没问题
