二分查找——函数实现

二分查找：

在一组有序的数组中，如果要查找某一元素，最简单的方法就是从第一个元素开始找到最后一个元素，最坏的情况就是最后才找到，因此不高效；于是我们可以改成二分查找（前提：一定要是有序的），即每次看中间元素与要查找的元素的大小关系，然后每次排除掉另一半元素，再进行选出来的一半的中间值与要查找的元素的大小比较，如此类推直到找到为止。每次都能排除一半的元素，比起一个一个查找要高效不少，数据越大越高效得明显；

答案：

#include<stdio.h>
int bin_search(int arr[], int left, int right, int key)
{
	int i = 0;
	while (left <= right)     //当还能继续二分查找时
	{
		int mid = (left + right) / 2;   //用数组下标找中间值的下标
		if (key > arr[mid])   //如果该中间值比要查找的元素小，说明要查找的元素在中间值的右边
		{
			left = mid + 1;   //左起点下标就为中间值的下标加1（因为中间值mid已经不等于key，所以没必要在从mid开始查，直接+1）
		}
		else if (key < arr[mid])  //如果该中间值比要查找的元素大，说明要查找的元素在中间值的左边
		{ 
			right = mid - 1;    //右起点下标就为中间值的下标减1（因为中间值mid已经不等于key，所以没必要在从mid开始查，直接-1）
		}
		else   //如果该中间值就是要查找的元素
		{
			return mid;   //返回中间值
		}
	}
	return -1;   //如果用二分法将所有元素都找了一遍还没有找到
}
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int left = 0, right = (sizeof(arr)/sizeof(arr[0]))-1, key = 0;
	printf("请输入你想查找的数值：\n");
	scanf("%d", &key);
	int an=bin_search(arr, left, right, key);
	if (an >= 0)    //如果能返回正常的下标
		printf("你想查找的数值的下标为：%d\n", an);
	else   //如果返回的是-1
		printf("找不到该元素，%d", an);
	return 0;
}