??引言??
【算法系列|【算法基础1】舍友课间上了个厕所,回来就告诉我他掌握了二分查找【内附搜索模板】】大家好,我是执梗。前两天写了篇关于蓝桥杯的文章,收到了很多兄弟们的反响。如果还有想参加蓝桥杯兄弟们没有看过的一定要看看哈——蓝桥杯。关于兄弟们的许多问题我都有看,为了帮助兄弟们,准备搞个算法系列,今天先说说二分查找,希望大家多多支持。
博客首页:执梗的博客??小剧场??
欢迎关注点赞收藏??留言
?? :热爱Java学习,期待一起交流!
作者水平很有限,如果发现错误,求告知,多谢!
有问题可私信交流!!!
有?天阿强到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把阿强拦下,要检查?下哪本书没有登记出借。阿强正准备把每?本书在报 警器下过?下,以找出引发警报的书,但是保安露出不屑的眼神:你连?分查找都不会吗?于是保安把书分成两堆,让第?堆过?下报警器,报警器响;于是再把这堆书分成两堆…… 最终,检测了 logN 次之后,保安成功的 找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是阿强背着剩下的书?了。 从此,图书馆丢了 N - 1 本书。
文章图片
1.什么是二分查找(折半查找)? 二分查找又叫做折半查找。上面小剧场的例子是一个小玩笑哈哈哈,不过却是一个能让人立马理解什么是二分思想的好例子。再说一个猜数字的游戏,大家刚开始学编程很多都玩过,设置一个随机数去慢慢猜,由程序来告诉你猜的数是大了还是小了,直到猜对为止(大家肯定没有从1慢慢去猜的吧)。没有玩过的我也特地找了个题目的链接:猜数字大小。所以其实二分的思想我们一直都在使用,只不过没有去尝试过把它运用到我们写的程序中去。
二分查找的思想虽然简单,但运用程序写起来却并不容易。Knuth ?佬(发明 KMP 算法的那位)都说?分查找:思路很简单,细节是魔鬼。因为你会发现你每次写二分都会纠结:这个mid到底是加一还是减一,whlie到底用<=还是<。所以我将写出模板后,跳出细节的地方为大家讲解。同样还需要注意的是,希望大家尽量写二分查找时都写成if else-if的形式,这样的可读性更强,把每个条件都写出来,细节展现出来,这样更容易去理解。2.最基础二分:查找一个数
题目:给定一个int类型的升序数组nums,请你判断一个数target是否在nums中,如果在请返回k的下标,否则返回-1;
题目链接:力扣:二分查找
public int binarySearch(int[] nums, int target) {//二分查找最基础模板
int left = 0;
//left是搜索区间的左边界
int right = nums.length - 1;
//right是搜索区间的右边界
while (left <= right) {//细节1
int mid = left + (right - left)/2;
//细节2
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
// 细节3
else if (nums[mid] > target)
right = mid - 1;
// 细节4
}
return -1;
}
??解析细节2:为什么mid不写成right+left/2?为什么都知道int类型是有范围的,我们的mid是为了获取right和left的中间值。我们先将right+left,如果这两个数都特别特别大,这时候就会整型溢出出错。所以我们要养成写成left + (right - left)/2的好习惯。结果当然是一样的哈(不相信的自己手动化简一下,都是大学生了应该会吧哈哈哈)
??解析细节1:为什么要用<=不写错 首先我们要明确搜索区间这个概念,我们的right初始值是 nums.length - 1而不是nums.length。所以当我们写的是<=,那我们搜索的区间是[left,right]。因为如果你写成<那就是搜索区间就变成是[left,right)。有区别吗?当然有区别,难道我的target不会在right(注意right最开始是nums.length-1)这个下标处吗?当然会啦!那你的搜索区间肯定要包括right这个位置啦!
??解析细节3,4:为什么不写成left=mid或者right=mid?还是说出到那个问题,搜索区间!!mid是否加1的问题,无非就是我们到底要不要把mid放到下一个搜索区间中 。我们看代码,在上面我们都是先判断target==nums[mid],当mid不是我们查找的元素时,它才会继续,那我们还要把mid放到下个搜索区间吗?当然不用啦!因为我们要将mid排除在外 ,所以要写成mid+1或者mid-1。
??解析循环结束条件:任何一个二分查找,你一定要明确自己的循环会在什么时候结束。上面的代码中我们结束的条件有两个。1、我们找到目标数target,也就是nums[mid] == target满足。2、搜索区间[0,nums.length-1]全部判断完毕,即当数组搜索完了都还没找到这个数2.基础二分的缺陷和局限性 上面的基础二分查找,是有着一定的局限性的。假如给你一个nums=[2,3,3,3,4]的数组,而target为2时,通过基础二分你可以获得索引为2,这确实没错。但是,如果题目要求的是target第一次出现的索引的位置呢?或者是最后一次出现的索引的位置呢?再甚者是要你找出第一次和最后一次出现的索引的位置呢?咋办?这样的要求是非常常见的。有的同学说向左右两边摸索过去找到边界,那你用二分的意义就变了。所以我们要学会去搜索左边界和搜索右边界。但是初学者却难以去掌握,所以我为大家总结了左右边界的模板供大家直接使用(在掌握基础二分后去体会我标明细节处的变化)
3.寻找左侧边界的二分查找
public int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
// 细节1
while (left < right) { // 细节2
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
// 细节3
}
}
return left;
}
4.寻找右侧边界的二分查找
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1;
// 细节1
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1;
// 细节2
}
4.二分查找经典例题 1.搜索插入的位置
2.在排序数组中查找元素的第一个和最后一个位置
3.寻找比目标字母大的最小字母
4.旋转数组的最小数字
5.搜索旋转排序数组
如果觉得有用的兄弟千万别忘记给个三连,感谢!
文章图片
推荐阅读
- java|自学java(2)
- 数据库|MySQL数据库
- 我的故事|舍友一个月做出的游戏,一天被我破解了(硬核知识)
- leetcode刷题实录|leetcode226 翻转二叉树
- 数组|二、数据结构与算法 稀疏数组
- 刷题|leetcode226翻转二叉树(JAVA版)
- leetcode|LeetCode226翻转二叉树(递归)
- 算法学习|最近公共祖先之树上倍增求法
- 蓝桥杯|蓝桥杯素数(二)