【C语言】二分查找法

二分查找也称折半查找（Binary Search），要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

在一个1-10的有序数组中查找数字7：

#include<stdio.h>
 
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;
	int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素个数
	int left = 0;
	int right = sz - 1;
 
	while (left <= right)
	{
		//int mid = (left + right) / 2;当数值太大可能出现溢出问题
		int mid = left + (right - left) / 2;//不会出现溢出问题
 
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是:%d\n", mid);
			break;
		}
	}
	if (left > right)
		printf("找不到\n");
 
	return 0;
}

二分查找法函数形式：

#include <stdio.h>
 
int binary_search(int arr[], int k, int sz)
	int left = 0;
	int right = sz - 1;
 
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			return mid;//找到了返回下标
		}
	}
	return -1;//找不到返回-1，不能返回0因为找到了返回的下标可能是0
}
 
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("找到了，下标是：%d\n", ret);
	}
 
	return 0;
}
//结果为：找到了，下标是：6

int sz = sizeof(arr) / sizeof(arr[0]);不能放在binary_search函数内。数组传参实际上传递的是数组首元素的地址，而不是整个数组，所以不能在函数内部计算一个函数参数部分的数组的元素个数。形参arr看上去是数组，本质是指针变量。