算法系列|【算法基础1】舍友课间上了个厕所,回来就告诉我他掌握了二分查找【内附搜索模板】

??引言??
【算法系列|【算法基础1】舍友课间上了个厕所,回来就告诉我他掌握了二分查找【内附搜索模板】】大家好,我是执梗。前两天写了篇关于蓝桥杯的文章,收到了很多兄弟们的反响。如果还有想参加蓝桥杯兄弟们没有看过的一定要看看哈——蓝桥杯。关于兄弟们的许多问题我都有看,为了帮助兄弟们,准备搞个算法系列,今天先说说二分查找,希望大家多多支持。

博客首页:执梗的博客
欢迎关注点赞收藏??留言
?? :热爱Java学习,期待一起交流!
作者水平很有限,如果发现错误,求告知,多谢!
有问题可私信交流!!!
??小剧场??
有?天阿强到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把阿强拦下,要检查?下哪本书没有登记出借。阿强正准备把每?本书在报 警器下过?下,以找出引发警报的书,但是保安露出不屑的眼神:你连?分查找都不会吗?于是保安把书分成两堆,让第?堆过?下报警器,报警器响;于是再把这堆书分成两堆…… 最终,检测了 logN 次之后,保安成功的 找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是阿强背着剩下的书?了。 从此,图书馆丢了 N - 1 本书。
算法系列|【算法基础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:为什么要用<=不写错
??解析细节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.搜索旋转排序数组
如果觉得有用的兄弟千万别忘记给个三连,感谢!
算法系列|【算法基础1】舍友课间上了个厕所,回来就告诉我他掌握了二分查找【内附搜索模板】
文章图片



    推荐阅读