C语言-折半查找（二分查找）算法详解

目录

题目：用折半查找在一个有序数组中查找一个具体的数字n

---

题目：用折半查找在一个有序数组中查找一个具体的数字n

为了方便讲解，我们假设这里的有序数组是arr[ ] = {1,2,3,4,5,6,7,8,9,10}，要查找的数是 7 。

第一步，我们标出这个有序数组的下标，并找出最左边、最右边和中间的下标：

 由图可见，下标left = 0，mid = 4，right = 9。

第二步，将下标为 mid 的数字与要查找的数字 7 进行比较：

   此时因为 arr[mid] = 5 < 7,所以令 left = mid +1 = 5,right = 9不变，此时 mid = (5 + 9)/2 =7。这就缩小了一半的查找范围。

第三步，继续将要下标为 mid 的数与要查找的数字 7 进行比较：

  此时因为 arr[mid] = 8 > 7,所以令 left = 5不变，right = mid - 1 = 6，此时mid = (5 + 6 )/2 = 5。再次缩小一半的查找范围。

第四步，继续将要下标为 mid 的数与要查找的数字 7 进行比较：

   此时因为 arr[mid] = 6 < 7,所以令 left = right + 1 = 6，right = 6 不变，此时mid = (6 + 6)/2 = 6,

mid = left = right，下次再查找就可以找到了。

  这就是折半查找法的具体查找步骤，其中比较元素大小的部分，分为arr[mid] < 7,arr[mid] > 7，和arr[mid] = 7这三种情况，我们可以用 if else 分支语句实现，多次查找用 while 循环语句实现，将它们嵌套在一起就可以实现在一个有序数组中查找一个具体的数。

下面附上代码：

#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	//假设数组是{1,2,3,4,5,6,7,8,9,10}
	int n = 7;//要查找的数
	int m = sizeof(arr) / sizeof(arr[0]);//计算数组长度
	int right = m - 1;//右边下标
	int left = 0;//左边下标
	while (left <= right)
	{
		int mid = (left + right) / 2;//中间元素的下标
		if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else if (arr[mid] > n)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是%d\n", mid);
			break;
		}
		if (left > right)
		{
			printf("找不到了\n");
		}
	}
	return 0;
}

  代码中int m = sizeof(arr) / sizeof(arr[0]);用来计算数组长度，sizeof(arr)是整个数组的大小，sizeof(arr[0])是下标为0的数组元素的大小，用整个数组大小除以下标为0的数组元素的大小即可计算出数组长度。