对半查找（折半查找）

//非递归方式解决

#include <stdio.h>

//返回下标 
int binary_search(int *pdata,int size,int x)
{
    
	int low,hight,mid;
	
	low = 0;
	hight = size-1;
	while(low <= hight)
	{
    
		mid = (hight + low)/2;
		if (pdata[mid] < x)
		{
    
			low = mid + 1;
		}else if (pdata[mid] > x)
		{
    
			hight = mid - 1;
		}else
		{
    
			return mid;
		}
	}
	return -1;
} 

//递归方法解决

//递归方法 
int binary_search_recursion(int *pdata,int hight,int low,int x)
{
    
	int mid=0;
	
	if (low > hight)
	{
    
		printf("-1hight;%d-low:%d\r\n",hight,low);
		return -1;
	}
	//printf("hight;%d-low:%d\r\n",hight,low);
	
	mid = (hight + low)/2;
	
	if (pdata[mid]<x)
	{
    
		binary_search_recursion(pdata,hight,mid + 1,x);
	} else if (pdata[mid]>x)
	{
    
		binary_search_recursion(pdata,mid - 1,low,x);
	}else
	{
    
		return mid;
	}

	
} 

//测试代码

int main(int argc, char *argv[])
{
    
	int result;
	#define BUF_SIZE 10
	int buf[BUF_SIZE] = {
    1,3,5,7,9,11,13,15,17,20};
	
	//result = binary_search(buf,BUF_SIZE,20);
	result = binary_search_recursion(buf,9,0,20);
	printf("result:%d\r\n",result);
	
	//result = binary_search(buf,BUF_SIZE,19);
	result = binary_search_recursion(buf,BUF_SIZE-1,0,19);
	printf("result:%d\r\n",result);
	
	result = binary_search_recursion(buf,BUF_SIZE-1,0,1);
	printf("result:%d\r\n",result);
	return 0;
}

运行结果