c语言——二分查找（折半查找）实现

#include

int binary_search(int arr[],int k,int sz) 
//这里数组实质上是一个指针
{
	//折半查找
	//int sz = sizeof(arr)/sizeof(arr[0]);  //求不出数组长度
	int low = 0;  //数组下标从0开始
	int high = sz - 1; 
	int mid = 0;  //中间元素下标
	
	while(low <= high)
	{
		mid = (low + high)/2; //取下界
		if(k == arr[mid])
			return mid;
		else if(k < arr[mid])
			high = mid - 1;
		else 
			low = mid + 1;
	}
	return -1;
}

int main()
{
	int arr[] = {1,2,3,4,5,6,7,8,9,10};
	int k = 7;
	int sz = sizeof(arr)/sizeof(arr[0]);

	int ret = binary_search(arr,k,sz);
	//数组传参时只传入第一个元素的地址
	if(ret == -1)
		printf("找不到n");
	else
		printf("找到了，下标为%dn ",ret);
	return 0;
}

注意：在binary_search()函数体内求数组的长度时，得不到实际的数组长度。因为在传入参数时，数组只传入了首元素的地址，实质上是一个指针，所以在binary_search()函数体内求数组长度，求的是仅含首元素的长度。解决方法：在main()函数内先求出数组长度，再传给binary_search()函数。