【基础算法】二分法查找

    如果序列A已经排好序，就可以将该序列的中点与v进行比较，根据比较结果，原序列A中的一半就不用再进一步考虑了，二分查找算法重复此操作，每次都将剩余的部分规模减半（分治法的思想）。

    二分法查找的最坏情况运行时间为Θ(lgn)。

    代码如下：

#include <stdio.h>
int Recurbinary (int * a,int p,int r,int v);

int main ()
{
	int a[9]={1,2,3,4,5,6,7,8,9};
	int v=2;
	int re;
	re=Recurbinary(a,0,8,v);
	if(re==-1)
	{
		printf("no find");
	}
	else
	{
		printf("find the number %d in %d\n",v,re);
	}

	return 0;
}

//p为数组的下限，r为数组的上限，v为要查找的值
int Recurbinary (int * a,int p,int r,int v)
{
	int mid;
	
	if(p>r)
	{
		return -1;
	}
	mid=(p+r)/2;
	if(a[mid] == v)
	{
		return mid;
	}
	else if(v>a[mid])
	{
		return Recurbinary(a,mid+1,r,v);
	}
	else
	{
		 return Recurbinary(a,0,mid-1,v);
	}

}