【ARTS】【LeetCode-704】二分查找算法

目录

前言

什么是ARTS？

算法

力扣704题

二分查找

基本思想：

二分查找算法(递归的方式):

经典写法(找单值):

代码分析:

经典写法(找数组即多个返回值)

代码分析

经典题目

题目描述：

官方题解

深入思考

模版一 (相错终止/左闭右闭)

相等返回情形

情形1 (大于等于)

情形2 (大于)

情形3 (小于等于)

情形4 (小于)

模版二 (相等终止/左闭右开)

相等返回情形

情形1 (大于等于)

情形2 (大于)

情形3 (小于等于)

情形4 (小于)

从「y总模版」到「模版二」之「左开右闭」

相等返回情形

情形1 (大于等于)

情形2 (大于)

情形3 (小于等于)

情形4 (小于)

模版三 (相邻终止/左开右开)

相等返回情形

情形1 (大于等于)

情形2 (大于)

情形3 (小于等于)

情形4 (小于)

参考资料：

---

前言

仅做学习使用，侵删

什么是ARTS？

算法(Algorithm): 每周至少一道LeetCode算法题，加强编程训练和算法学习

阅读(Review)： 阅读并点评至少一篇英文技术文章，提高英文水平

技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点

分享(Share)：分析一篇有关点和思考的技术文章，建立影响力，输出价值观

算法

力扣704题

一道经典的二分查找题目

链接:704. 二分查找 - 力扣（LeetCode）

二分查找

基本思想：

二分查找算法(递归的方式):

1. 创建一个查找算法,参数列表有left,right,findValue,array
2. 创建一个变量mid,通过left和right获取mid
3. 通过对mid的比较,决定递归方向
4. 最后判断是否能找到

经典写法(找单值):

public static int binarySearchSingle(int[] array,int left,int right,int findValue) {if(left > right || findValue > array[length-1]) {return -1;}var mid = left + 1/2*(right - left);var midValue = array[mid];if(findValue > midValue) {return binarySearchSingle(array,mid+1,right,findValue);}else if(findValue < midValue) {return binarySearchSingle(array,left,mid-1,findValue);}else {return mid;}}

代码分析:

1. left是左索引,right是右索引,应该一开始就被赋值为0与array.length-1(因为带查找的值在他们两个索引之间,即[left,right]区间内有带查找元素)
2. findValue是待查找的值,array是带查找的数组
3. 二分查找法顾名思义是折半,所以mid = 1/2(left + right) = left + 1/2*(right - left)

注意:后面的表达式非常的重要,是折半查找发的关键

1. 将mid下标对应的值放入midValue

情况:

1. 如果midValue大于findValue,由于有序,说明待查找的元素在mid右边且不为mid,所以得出了[mid+1,right]的范围内有带查找元素,故left = mid+1
2. 如果midVvalue小于findValue,由于有序,说明带查找的元素在mid左边且不为mid,所以得出了[left,mid-1]的范围内有带查找元素,故right = mid-1
3. 如果midValue = findValue,说明找到了该元素,直接返回mid即可,mid是下标
4. 如果left > right,由于没有这样的区间(即区间左边必须小于右边的值),说明找不到,直接返回-1
5. 如果findValue大于列表的最后一个值,由于有序,最后一个值为最大值,说明列表里面不可能有与findValue相同的值,直接返回-1

经典写法(找数组即多个返回值)

 public static List<Integer> binarySearchMore(int[] array,int left,int right,int findValue) {if(left > right || findValue > array[length-1]) {return new ArrayList<Integer>();}var mid = (left + right)/2;var midValue = array[mid];if(findValue > midValue) {return binarySearchMore(array,mid+1,right,findValue);}else if(findValue < midValue) {return binarySearchMore(array,left,mid-1,findValue);}else {var list = new ArrayList<Integer>();list.add(mid);var temp = mid - 1;while(temp > 0 && array[temp] == findValue) {list.add(temp--);}temp = mid + 1;while (temp < array.length && array[temp] == findValue) {list.add(temp++);}return list;}

代码分析

1. 注意:由于其他代码都一样,我们重点分析一下else里面的代码
2. 当程序进入else时,说明找到了该元素,由于我们要实现多元素返回,我们可以借助集合,故我们要new一个ArrayLsit<Integer>
3. 先将该元素add进去集合中
4. 创建一个辅助索引temp,赋值为mid-1(目的:向左遍历)
5. 通过while循环,如果temp>0(防止数组下标越界异常),且array[temp] = findValue,说明此元素也是我们要找的元素,添加入集合中
6. 如果while布尔表达式为false,说明temp遍历到了最左边或是不相等,由于列表的有序性,如果不相等,则前面的元素一定比midValue小,不可能再有带查找的元素,直接结束向左遍历
7. temp赋值为mid+1(目的:向右遍历)
8. 同理5~6
9. 最后返回list即可
10. 特别注意的是,如果找不到,我们返回一个空的集合,所以在最前面new了一个空集合

经典题目

题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。示例 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提示：你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

官方题解

class Solution {public int search(int[] nums, int target) {int left = 0,right = nums.length - 1;while (left <= right){int mid = (right - left) / 2 +left;int num = nums[mid];if (num == target) {return mid;} else if (num > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
}

深入思考

二分查找本身思想比较简单，但是实际上二分查找在编写的过程中会出现各种各样的问题，如无限循环等，针对这道题可能会不会有这种问题。特别是根据上下边界指针的循环确定问题。下面给出四种情形下的模版参考，每一种模版下又分为四种情况

以下资料参考 二分查找从入门到入睡 - 力扣（LeetCode）推荐去阅读原文，这里只是做摘录，给出对应情况的模版，具体分析参考原文，也可点击对应的模版链接直接跳转。
作者：yukiyama
链接： https://leetcode.cn/circle/discuss/ooxfo8/
来源：力扣（LeetCode）

模版一 (相错终止/左闭右闭)

相等返回情形

// 模版一「相等返回」写法
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l <= r){ // 循环条件int c = l + (r - l) / 2; // 中间值坐标if(nums[c] == target) return c; // 相等返回else if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于targetelse r = c - 1; // #2 更新后r右侧元素「必」大于target }return -1; }
}

情形1 (大于等于)

// 模版一「一般」情形1: 大于等于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l <= r){int c = l + (r - l) / 2;if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于targetelse r = c - 1; // #2 更新后r右侧「必」大于等于target}// return (l == nums.length || nums[l] != target) ? -1 : l; // 704题的返回，处理:相等/不等return l == nums.length ? -1 : l; // 处理: 相等/刚好大于/不存在}
}

情形2 (大于)

// 模版一「一般」情形2: 大于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l <= r){int c = l + (r - l) / 2;if(nums[c] <= target) l = c + 1; // #1 更新后l左侧元素「必」小于等于targetelse r = c - 1; // #2 更新后r右侧「必」大于target}return l == nums.length ? -1 : l; // 处理: 刚好大于/不存在}
}

情形3 (小于等于)

// 模版一「一般」情形3: 小于等于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l <= r){int c = l + (r - l) / 2;if(nums[c] <= target) l = c + 1; // #1 更新后l左侧「必」小于等于targetelse r = c - 1; // #2 更新后r右侧「必」大于target}// return (r == -1 || nums[r] != target) ? -1 : r; // 704题的返回，处理:相等/不等return r; // 处理: 相等/刚好小于/不存在}
}

情形4 (小于)

// 模版一「一般」情形4: 小于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l <= r){int c = l + (r - l) / 2;if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于targetelse r = c - 1; // #2 更新后r右侧「必」大于等于target}return r; // 处理: 相等/刚好小于/不存在}
}

模版二 (相等终止/左闭右开)

相等返回情形

// 模版二「相等返回」写法
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length;while(l < r){int c = l + (r - l) / 2;if(nums[c] == target) return c; // 找到目标值直接返回else if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target else r = c; // nums[c] > target #2 更新后r及其右侧「必」大于target}return -1;}
}

情形1 (大于等于)

// 模版二「一般」情形1: 大于等于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length;while(l < r){int c = l + (r - l) / 2;if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target else r = c; // #2 更新后r及r右侧「必」大于等于target}// return (r != nums.length && nums[r] == target) ? r : -1; // 704题的返回，处理:相等/不等return r != nums.length ? r : -1; // 处理:等于/刚好大于/不存在}
}

情形2 (大于)

// 模版二「一般」情形2: 大于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length;while(l < r){int c = l + (r - l) / 2;if(nums[c] <= target) l = c + 1; // #1 更新后l左侧「必」小于等于target else r = c; // #2 更新后r及其右侧「必」大于target}return r == nums.length ? -1 : r; // 处理:刚好大于/不存在}
}

情形3 (小于等于)

// 模版二「一般」写法之情形3(正确版2)
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length;while(l < r){int c = l + (r - l) / 2;if(nums[c] <= target) l = c + 1; // #1 更新后l左侧元素「必」小于等于target else r = c; // #2 更新后r及其右侧「必」大于target}// 原先针对 704 的返回有漏洞，该修改（下面一行）来自 Hankai Xia @masterx89 同学，感谢// return (r > 0 && nums[r - 1] == target) ? r - 1 : -1; // 704题的返回，处理:相等/不等// return r - 1; // 通过分析target的三种情形得到的统一返回值return r > 0 ? r - 1 : -1; // 但写成此种形式，逻辑更佳 （来自Hankai Xia @masterx89 的建议）}
}

情形4 (小于)

// 模版二「一般」情形4: 小于
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length;while(l < r){int c = l + (r - l) / 2;if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target else r = c; // #2 更新后r及其右侧「必」大于等于target}return r - 1; // 处理:刚好小于/不存在}
}作者：yukiyama
链接：https://leetcode.cn/circle/discuss/ooxfo8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

从「y总模版」到「模版二」之「左开右闭」

相等返回情形

// 模版二(左开右闭)相等返回情形
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length - 1;while(l < r){int c = l + (r - l + 1) / 2;if(nums[c] == target) return c;if(nums[c] < target) l = c; // #1 更新后l及l左侧元素「必」小于target else r = c - 1; // #2 更新后r右侧「必」大于target}return -1; // 704题的返回}
}

情形1 (大于等于)

// 模版二(左开右闭)「一般」情形1(大于等于)
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length - 1;while(l < r){int c = l + (r - l + 1) / 2;if(nums[c] < target) l = c; // #1 更新后l及l左侧元素「必」小于target else r = c - 1; // #2 更新后r右侧「必」大于等于target}// return (r == nums.length - 1 || nums[r + 1] != target) ? -1 : r + 1; // 704题的返回，处理:相等/不等return r == nums.length - 1 ? -1 : r + 1;}
}

情形2 (大于)

// 模版二(左开右闭)「一般」情形2(大于)
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length - 1;while(l < r){int c = l + (r - l + 1) / 2;if(nums[c] <= target) l = c; // #1 更新后l及l左侧元素「必」小于等于target else r = c - 1; // #2 更新后r右侧「必」大于target}return r == nums.length ? -1 : r + 1;}
}

情形3 (小于等于)

// 模版二(左开右闭)「一般」情形3(小于等于)
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length - 1;while(l < r){int c = l + (r - l + 1) / 2;if(nums[c] <= target) l = c; // #1 更新后l及l左侧元素「必」小于等于target else r = c - 1; // #2 更新后r右侧「必」大于target}// return (l == -1 || nums[l] != target) ? -1 : l; // 704题的返回，处理:相等/不等return l;}
}

情形4 (小于)

// 模版二(左开右闭)「一般」情形4(小于)
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length - 1;while(l < r){int c = l + (r - l + 1) / 2;if(nums[c] < target) l = c; // #1 更新后l及l左侧元素「必」小于target else r = c - 1; // #2 更新后r右侧「必」大于等于target}return l;}
}

模版三 (相邻终止/左开右开)

相等返回情形

// 模版三「相等返回」写法
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length;while(l + 1 < r){int c = l + (r - l) / 2;if(nums[c] == target) return c; // 找到目标值直接返回else if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target else r = c; // nums[c] > target #2 更新后r及其右侧「必」大于target}return -1;}
}

情形1 (大于等于)

// 模版三「一般」情形1: 大于等于
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length;while(l + 1 < r){int c = l + (r - l) / 2;if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于targetelse r = c; // #2 更新后r及其右侧「必」大于等于target}// return (r == nums.length || nums[r] != target) ? -1 : r; // 704题的返回，处理:相等/不等return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在}
}

情形2 (大于)

// 模版三「一般」情形2: 大于
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length;while(l + 1 < r){int c = l + (r - l) / 2;if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于targetelse r = c; // #2 更新后r及其右侧「必」大于target}return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在}
}

情形3 (小于等于)

// 模版三「一般」情形1: 大于等于
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length;while(l + 1 < r){int c = l + (r - l) / 2;if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于targetelse r = c; // #2 更新后r及其右侧「必」大于等于target}// return (r == nums.length || nums[r] != target) ? -1 : r; // 704题的返回，处理:相等/不等return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在}
}

情形4 (小于)

// 模版三「一般」情形4: 小于
class Solution {public int search(int[] nums, int target) {int l = -1, r = nums.length;while(l + 1 < r){int c = l + (r - l) / 2;if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于targetelse r = c; // #2 更新后r及其右侧「必」大于等于target}return l;}
}

拿到题目可以直接对题目进行分析，按照情形套用对应的模板

下面是一些题目

本节给出如下二分查找题目，在理解本文内容后，应当不难做出。「题解」一列中给出了相应的题解以供读者自查。

704. 二分查找简单题解

69. x 的平方根简单题解

374. 猜数字大小简单题解

剑指 Offer 53 - II. 0～n-1中缺失的数字简单题解

33. 搜索旋转排序数组中等题解

153. 寻找旋转排序数组中的最小值中等题解

154. 寻找旋转排序数组中的最小值 II困难题解

81. 搜索旋转排序数组 II中等题解

278. 第一个错误的版本简单题解

162. 寻找峰值中等题解

34. 在排序数组中查找元素的第一个和最后一个位置中等题解

35. 搜索插入位置简单题解

74. 搜索二维矩阵中等题解

658. 找到 K 个最接近的元素中等题解

29. 两数相除中等题解

875. 爱吃香蕉的珂珂中等题解

668. 乘法表中第k小的数困难题解

462. 最少移动次数使数组元素相等 II中等题解

436. 寻找右区间中等题解

528. 按权重随机选择中等题解

497. 非重叠矩形中的随机点中等题解

240. 搜索二维矩阵 II中等题解

4. 寻找两个正序数组的中位数困难题解

参考资料：

1. 二分查找从入门到入睡 - 力扣（LeetCode）
2. 代码随想录
3. 704. 二分查找 - 力扣（LeetCode）