二分查找【多种方法+图解】

(二分查找【多种方法+图解】)

前言

二分查找其实是一个十分容易理解的方法，在很多人思路里都知道先这个..再那个....，其实二分查找也有许多细节需要去细细分析

介绍以及简单思路介绍

二分查找是对于一个有序数组进行查找，如果数组无序，可以通过最简单的冒泡排序去排序

• 1找到数组的中间位置
• 检查中间位置的数组是否与要查找的数据key相等
  • a: 相等，就找到，打印下标跳出循环
  • b: key<arr[mid]，则key可能在arr[mid]的左半侧，继续到左半侧进行二分查找
  • c: key》arr[mid]，则key可能在arr[mid]的右半侧，继续到右半侧进行二分查找
• 如果找到，打印下标，否则继续，直到区间中没有元素时，说明key不在集合中

可见这里的中间值是一个十分重要的值，对于求这个中间的值还有一个小细节： left为数组左下标，right为数组右下标 提到求中间值，我们第一时刻就会想到：int mid = (left+right)/2,这样在一般情况下是没有问题的 但是int类型是有它的范围的，有可能两个int类型的值相加的值就会超过int的最大范围值，也就是溢出 所以这里我们最好这样写：int mid = left + (right - left) / 2,这样就会避免溢出，其实把这个式子进行通分，就会得出(left+right)/2这个式子，他们的本质实际是一样的，只是后者避免溢出而已

接下来有两种解法，我们要注意三点：

1. right的右半侧区间取值，决定了后续的写法
2. while循环条件是否有等号
3. 更改right和left的边界时，是否要+1和-1

第一种解法，[left,right]区间

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int key = 0;
	scanf("%d" ,&key);
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[1]) - 1;
	
	while (left <= right) //right位置有元素，要添加=号
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] > key)
		{
			right = mid - 1;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下标是：%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到\n");
	}
	return 0;
}

在while的循环条件是left <= right，就是哪怕left==right时，也会再循环一次 如果情况如下图时，也会再有一次循环去得到mid的值，如果判断条件是left<right时，则下图的情况则会退出循环，找不到要找的值

在改变left和right的边界时，如果arr[mid] > key就·right = mid - 1若arr[mid] < key，就left = mid + 1这很容易理解，这也是人们通常最容易想出的一个二分查找

下面做一个例子 在{1,5,6,10,15,20,30,35}中，查找20

arr[mid]==key==20查找成功

第二种解法，[left,right)区间

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int key = 0;
	scanf("%d", &key);
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[1]);

	while (left < right) 
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] > key)
		{
			right = mid;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下标是：%d\n", mid);
			break;
		}
	}
	if (left >= right)
	{
		printf("找不到\n");
	}
	return 0;
}

要注意的是：这里的right的初始值为sizeof(arr) / sizeof(arr[1])为数组的长度，实际上是数组最后一个的下标的下一位

这里的while中的判断语句是left < right，若arr[mid] < key，就left = mid + 1这里和上一个解法相同，arr[mid] > key 就right =mid这里与上一解法不同

递归解法

void find(int* arr, int n, int left, int right)
{
	if (left <= right)
	{
		int mid = left+(right-left)/2;
		if (n == arr[mid])
		{
			printf("找到了%d它在下标%d处",n,mid);
		}
		else if (n > arr[mid])
		{
			find(arr, n, mid + 1, right);
		}
		else
		{
			find(arr, n, left, mid - 1);
		}
	}
	if (left > right)
	{
		printf( "没找到");
	}
}

int main()
{
	int arr[10] = { 5,8,10,26,74,100,102,120,136,180};
	int len = sizeof(arr) / sizeof(arr[0]);
	int n1 = 0;
	int left = 0;
	int right = len - 1;
 	printf("输入你想要查找的数\n");
	scanf("%d",&n1);
	find(arr, n1, left, right);

	return 0;
}

这里原理和解法一相同，这里不多介绍