算法系列|【算法基础1】舍友课间上了个厕所，回来就告诉我他掌握了二分查找【内附搜索模板】双指针|Java|蓝桥杯|后端|算法

??引言??
【算法系列|【算法基础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.搜索旋转排序数组
如果觉得有用的兄弟千万别忘记给个三连，感谢！