c语言二分查找

前言

二分查找法算法，也叫折半查找算法（对半处理会提高寻找目标数字的效率）；作用： 在一串有序的数字中，能快速寻找到你输入的数字，是一种很高效的查询算法。

二分查找的具体思路

先取数组的中位数，然后将其跟我们需要查找的数字大小进行比较，如果它等于我们需要查找的数字，直接打印其下标即可；如果它小于我们需要查找的数字，我们就将范围缩小到中位数后面的数字；如果它大于我们需要查找的数字，我们就将范围缩小到中位数前面的数字。按照这样的运行规律我们可以知道当程序每查找一次就会，它的查找范围就会缩小一半，可想而知，当我们在一个很长的一串数字里面找到我们所需要的数字时，二分查找将会大大提高了计算机的查找效率。但是二分查找只能运用在升序数组中。

例题

写一个二分查找函数
功能：在一个升序数组中查找指定的数值，找到了就返回下标，找不到就返回 - 1.

int bin_search(int arr[], int left, int right, int key)
// arr 是查找的数组
//left 数组的左下标
//right 数组的右下标
//key 要查找的数字

思路

先用sizeof求出数组的元素个数，然后计算其中间值的下标mid。可以取数组查找范围中最左边的数下标为left，最右边的数为right。如果mid等于我们需要查找的数字，直接打印其下标即可；如果mid小于我们需要查找的数字，这时就可以让left=mid-1；如果mid大于我们需要查找的数字，这时就可以让right=mid+1；如果left>right则说明整个数组中没有我们需要查找的数。

完整代码

int bin_search(int arr[], int left, int right, int key)
{
	int mid = sizeof(arr) / sizeof(arr[0]) / 2 - 1;
	while (left <= right)
	{
		if (arr[mid] == key)
		{
			printf("找到了下标为:%d\n", mid);
			break;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
			mid = (left + right) / 2;
		}
		else
		{
			right = mid - 1;
			mid = (left + right) / 2;
		}
	}
	if (left > right)
	{
		printf("-1\n");
	}
}
int main()
{
	int s = 0;
	while (scanf("%d", &s) == 1)
	{
		int arr1[] = { 0,1,2,3,4,5,6,7,8,9 };
		int left = 0, right = sizeof(arr1) / sizeof(arr1[0]) - 1;
		bin_search(arr1,left,right,s);
	}
	return 0;
}