最详细的C语言二分法查找原理及实战

c语言中二分法查找是一个重难点，如何在一堆字符串（数字等等）中快速找到自己想要的？今天大家一起来掌握一下吧。

ps：这里只介绍有序的数，如果是无序的，可以用冒泡排序法先进行一下排序，这个后面会再详细介绍。

首先介绍一下二分法查找：

数组arr[10]里现有数字1 2 3 4 5 6 7 8 9 10，要查找7在哪里，如果用最简单暴力的查找方法，也就是从第一个数字开始要找7次，如果是非常大的数组，而找的数又非常大，这样的查找方法效率十分低下。

如果用二分法，我们已知1 2 3 4 5 6 7 8 9 10 对应下标分别为0 1 2 3 4 5 6 7 8 9 也就是说7对应的下标为6，1和10对应下标分别为0和9，进行一次求平均值，这里我们默认为int（0+9）/2=4,

4<6&&6<10那么我们下一次的查找的下标范围也就缩小成了5-9（4和10都不考虑了，范围是(4,10)区间的子区间，又因为是整数，可以认为是[5,9]）,进行第二次查找，5和9对应下标为4和8，进行一次求平均值，（4+8）/2=6正好是7对应的下标，7已经被找到。仅仅用了两次查找，相对于传统的查找方法二分法查找的简便性显而易见。

c语言二分法查找代码如下：

```c
#include <stdio.h>
int main()
{
	int arr[10] = {1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 7;
	int left = 0;
	int right = sz - 1;
	while (left <=right)
	{
		int mid = (left + right) / 2;//这里如果本行放在while外，那么mid会一直=(0+9)/2=4,进行一次查找后arr[4]=5<7,left=mid+1=5。left=5<9=right进入循环，arr[4]=5<7...以此循环下去，arr[mid]会永远小于k
    //上一行放while里面是为了，每进行一次循环，都可以重新定义mid
		if (arr[mid] < k)
		{
			left = mid+1;//arr[mid]<k,说明下标mid在k下标的左边，那么下一次查找应该在mid右边开始查，所以mid+1
		}
		else if (arr[mid] > k)
		{
			right = mid-1;//arr[mid]>k,说明下标mid在k下标的右边，那么下一次查找应该在mid左边开始查，所以mid-1
		}
		else//mid=k时候
		{
			printf("找到了，数%d,位置为arr[%d]", k,mid);
			break;//这里因为while条件是left<=right，当恰巧找到的最后一个数是要找的数，left=right=（left+right）/2=mid，这是会while一直循环下去,找到后要break跳出循环
		}
	}
	if (left > right)
	{
		printf("没有这个数%d", k);
	}
	return 0;
}
```