【C语言】二分查找

一. 二分查找基本思路

有序表中,每次都取中间元素作为比较的对象。

如果给中间值与给定值相等,则查找成功,返回该元素的下标/索引;

如果中间值大于给定值,则在中间值的右半区间继续查找;

如果中间值小于给定值,则在中间值的左半区间继续查找;

确定了该元素所在范围那么范围外的元素就不需要查找了,不断重复上诉过程,直至找到

因为二分查找每次查找都可以剔除一半的查找范围,所以相比顺序查找每次一个一个元素查找,查找效率提高了很多。

二分查找需要两个必要条件:

1.数组元素必须有序

2.查找的数值不能多个,只能一个

二. 详细图解

例如:给定一个有序数组 nums = {1,2,4,5,7,8,11,15} 中,求数字7所在数组中的下标

二分查找过程:

 (1)定义两个指针 left 和 right ;left 指向首元素的下标,right 指向最后一个元素的下标。 traget 为目标值。即:

bfe1b79a6995477cb84fac4372646a33.png

 (2)求中间元素的值mid,即:mid = left + (right – left) / 2 得到中间下标 通过中间下标可以访问到中间元素 nusm[mid] 。即:

d854ee8ef0014e45ab99c56b68010ef8.png

问题:求中间值为什么不用 mid = (left + right) / 2 呢?

原因:如果是两个较大的值,相加超过了 int 取值范围(2147483647)就会导致溢出

 (3)使用中间值 nums[mid] 和目标值 target 对比,此时 nums[mid] < target 就证明 nums[mid] 左边的值 和 nums[mid]的值都不需要继续对比了。然后将 left 指针移动到 mid+1 的位置,查找范围就是 [mid+1,right] 。即:

a1e6f6a775b945c5b03603c3d7fc360c.png

 (4)继续对比,发现 nums[mid] > target。证明 nums[mid] 的值 和 nums[mid] 右边的值都不需要对比了。就让 right 指针移动到 mid-1 的位置。即:

12b22687c5d44befb18315bcffa0e6ab.png

(5)现在 nums[mid] 和 target 相等,然后返回 mid ,查找结束

下面来看一道经典的二分查找例题,加深理解

三. 例题

题目:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

来源:力扣(LeetCode)

示例1:

输入:nums = [-1,0,3,5,9,12],target = 9

输出:4

解释:9 出现在 nums 中并且下标为 4

示例2:

输入:nums=[-1,0,3,5,9,12],target = 2

输出:-1

解释:2 不存在 nums 中因此返回 -1

1. 第一步

首先是在一个有序的数组中查找某个元素的,那就需要一个数组来存放一些 int 类型的数据,可以通过题目看到除了输入一个数组 nums 外,还需输入一个目标值 target 

#include <stdio.h>
void main() {
	int nums[] = {-1,0,3,5,9,12};
	int numsSize = sizeof(nums) / sizeof(nums[0]);//数组大小
	int target= 0;//目标值target
	scanf("%d",&target);
}

2.第二步

写一个二分查找函数,并且定义两个指针 left 和 right,left 为首元素的下标,right 为最后一个元素的下标, 然后求中间元素的下标 mid ( mid = left + (right – left) / 2) 即:

0da3dc4d200949f990751c8fe4edcc17.png

#include <stdio.h>
int binarySearch(int nums[],int numsSize,int target) {
	int left = 0;//首元素下标
	int right = numsSize - 1;//末元素的下标(总长度-1,数组从0开始)

	//int mid = (left + right) / 2;//如果是两个较大的值超过了int类型的取值范围就会导致溢出
	int mid = left + (right - left) / 2;//中间元素的下标 防止溢出

}
void main() {
	int nums[] = {-1,0,3,5,9,12};
	int numsSize = sizeof(nums) / sizeof(nums[0]);//数组长度
	int target= 0;//目标值target
	scanf("%d",&target);
	printf("%d", binarySearch(nums,numsSize, target));
}

3.第三步

使用中间元素和目标值(target)对比,假如target = 9,那么 中间元素(5) < 目标值(9),中间元素左半部分的值及中间元素本身也就没有必要继续对比了,此时的查找范围为[mid+1,right],也就是 left = mid + 1,right位置不变,即:

3c1d129692f14d1993c6c26d55b19518.png

问题: 如果我们查找的值是小于中间元素的时候呢?

回答:当 目标值 < 中间元素 时,就代表目标值在中间元素的左半部分,右指针就需要移动,也就是right = mid – 1,left不需要移动,此时查找范围为:[left,mid-1]。

大于和小于的情况都判断了,还有相等的情况,目标值 == 中间元素 时,就意味着找到该元素了,直接返回该下标即可。代码如下:

#include <stdio.h>
int binarySearch(int nums[],int numsSize,int target) {
	int left = 0;//首元素下标
	int right = numsSize - 1;//末元素的下标(总长度-1,数组从0开始)

	int mid = left + (right - left) / 2;//中间元素的下标 防止溢出
	int numsMid = nums[mid];//中间元素
	//目标值大于中间元素时
	if (numsMid < target) {
		//查找范围:[mid+1,right]
		left = mid + 1;
	}
	//目标值小于中间元素时
	else if (target < numsMid) {
		//查找范围:[left,mid-1]
		right = mid - 1;
	}
	else return mid;//相等时直接返回该元素下标

}
void main() {
	int nums[] = {-1,0,3,5,9,12};
	int numsSize = sizeof(nums) / sizeof(nums[0]);//数组长度
	int target = 0;//目标值target
	scanf("%d",&target);
	printf("%d", binarySearch(nums,numsSize, target));
}

4.第四步

最后就是重复执行上述过程了,每次都让目标值和中间元素对比,从而缩减查找范围,直至找到,如果没有的话返回-1

c80102db5f544adcb34bc4227bdf621c.png

注意:

1.在查找元素时 left 和 right下标会越来越近甚至指向同一个下标,过程中 left 始终在 right 的左边(即:left <= right)。

2.如果一直找不到那个元素,两个下标必然会相互交错(即: left > right),这时循环结束。所以循环条件就是:while(left <= right)

最终代码:

#include <stdio.h>
int binarySearch(int nums[],int numsSize,int target) {
	int left = 0;//首元素下标
	int right = numsSize - 1;//末元素的下标(总长度-1,数组从0开始)
	
	while (left <= right) {
		int mid = left + (right - left) / 2;//中间元素的下标 防止溢出
		int numsMid = nums[mid];//中间元素
		//目标值大于中间元素时
		if (numsMid < target) {
			//查找范围:[mid+1,right]
			left = mid + 1;
		}
		//目标值小于中间元素时
		else if (target < numsMid) {
			//查找范围:[left,mid-1]
			right = mid - 1;
		}
		else return mid;//相等时直接返回该元素下标
	}
	return -1;//没有找到目标值,返回-1
}
void main() {
	int nums[] = {-1,0,3,5,9,12};
	int numsSize = sizeof(nums) / sizeof(nums[0]);//数组长度
	int target = 0;//目标值target
	scanf("%d",&target);
	printf("下标:%d", binarySearch(nums,numsSize, target));
}

运行结果:

e923e15012d34240b362214da4acafcb.png

5.总结

 二分查找最重要的两个点,就是循环条件和后续的区间赋值问题

关于二分查找的讲解到这里就结束了,如果有什么不对的地方欢迎在评论区指正,谢谢支持~

dc0ddfa910464bf1aee7a88faf810f7c.jpeg

版权声明:本文为博主作者:EurekaO-O原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/qq_49663134/article/details/126079019

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
扎眼的阳光的头像扎眼的阳光普通用户
上一篇 2024年1月8日
下一篇 2024年1月8日

相关推荐

此站出售,如需请站内私信或者邮箱!