一. 二分查找基本思路
在有序表中,每次都取中间元素作为比较的对象。
如果给中间值与给定值相等,则查找成功,返回该元素的下标/索引;
如果中间值大于给定值,则在中间值的右半区间继续查找;
如果中间值小于给定值,则在中间值的左半区间继续查找;
确定了该元素所在范围那么范围外的元素就不需要查找了,不断重复上诉过程,直至找到
因为二分查找每次查找都可以剔除一半的查找范围,所以相比顺序查找每次一个一个元素查找,查找效率提高了很多。
二分查找需要两个必要条件:
1.数组元素必须有序
2.查找的数值不能多个,只能一个
二. 详细图解
例如:给定一个有序数组 nums = {1,2,4,5,7,8,11,15} 中,求数字7所在数组中的下标
二分查找过程:
(1)定义两个指针 left 和 right ;left 指向首元素的下标,right 指向最后一个元素的下标。 traget 为目标值。即:
(2)求中间元素的值mid,即:mid = left + (right – left) / 2 得到中间下标 通过中间下标可以访问到中间元素 nusm[mid] 。即:
问题:求中间值为什么不用 mid = (left + right) / 2 呢?
原因:如果是两个较大的值,相加超过了 int 取值范围(2147483647)就会导致溢出
(3)使用中间值 nums[mid] 和目标值 target 对比,此时 nums[mid] < target 就证明 nums[mid] 左边的值 和 nums[mid]的值都不需要继续对比了。然后将 left 指针移动到 mid+1 的位置,查找范围就是 [mid+1,right] 。即:
(4)继续对比,发现 nums[mid] > target。证明 nums[mid] 的值 和 nums[mid] 右边的值都不需要对比了。就让 right 指针移动到 mid-1 的位置。即:
(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) 即:
#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位置不变,即:
问题: 如果我们查找的值是小于中间元素的时候呢?
回答:当 目标值 < 中间元素 时,就代表目标值在中间元素的左半部分,右指针就需要移动,也就是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
注意:
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));
}
运行结果:
5.总结
二分查找最重要的两个点,就是循环条件和后续的区间赋值问题
关于二分查找的讲解到这里就结束了,如果有什么不对的地方欢迎在评论区指正,谢谢支持~
版权声明:本文为博主作者:EurekaO-O原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_49663134/article/details/126079019