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的数组元素的大小即可计算出数组长度。