【C语言】二分查找（折半查找）

目录

二分查找

1.简介

2.例子

3.代码如下

4.总结

二分查找

1.简介

二分查找也是有特殊情况的，比如数列本身是有序的。这个有序数列是怎么产生的呢？有时它可能本身就是有序的，也有可能是通过排序算法得到的。

不管其他情况，就先假设这一数组是有序的，接下来二分查找就该登场了。

二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。

2.例子

废话不多说，直接上例子：

假设已经排序好的一组数{5,12,15,19,22,35,36,40,67,78,82}

假设我们要找的元素是k=40；

 如图1，我们先找到这组数的第一个数和最后一个数的下标，定义第一个为 left，最后一个数为right，之后找到中间元素的下标 mid = left + (left+right) / 2，则 mid=35，把 mid=35 与 k=40 进行比较，发现 mid<k 并且这个数组是按照升序进行排序的，

所以可以判定如果数组中有 40 这个关键字，就一定存在于 mid 和 right 指向的区域中间。

 再次遍历时需要更新 left 和 mid 的位置，令 left 移动到 mid 的下一个位置上（也就是 mid+1 的位置上），同时令 mid 重新指向 left 和 right 的中间位置。如图 2 所示：

同样，用 mid 同 k 作比较，67 < 40，所以可以判定 40 如果存在，肯定处于 left 和 mid 指向的区域中。所以令 right 指向 mid 位置左侧的一个位置上(也就是 mid-1 的位置上)，同时更新 mid 的位置，如图3：

 同样，用 mid 同 k 作比较，36 > 40，所以可以判定 40 如果存在，肯定处于 mid 和 right 指向的区域中。所以令 left 指向 mid 位置右侧的一个位置上（也就是 mid+1 的位置上），同时更新 mid 的位置，如图4：

当第4次做判断时，发现 mid 就是关键字 21 ，查找结束

注意：在做查找的过程中，如果 left 和 right 的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。

3.代码如下

#include<stdio.h>
int main()
{
	int arr[] = { 5,12,15,19,22,35,36,40,67,78,82 };
	int k;
	scanf("%d", &k);
	int sz = sizeof(arr) / sizeof(arr[0]);//求数组长度
	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
		{
			printf("找到该数,下标是：%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到该数\n");
	}

	return 0;
}

4.总结

通过比较折半查找的平均查找长度，同顺序查找相对比，明显折半查找的效率要高。但是折半查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。

最后，文章到此结束啦！