音乐网站程序源码,海南省住房和城乡建设厅网站,上海网络优化服务,营销相关网站目录 前言 什么是ARTS#xff1f; 算法 力扣704题 二分查找 基本思想#xff1a; 二分查找算法(递归的方式): 经典写法(找单值): 代码分析: 经典写法(找数组即多个返回值) 代码分析 经典题目 题目描述#xff1a; 官方题解 深入思考 模版一 (相错终止/左闭右闭) 相等返回情形… 目录 前言 什么是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 二分查找 基本思想 二分查找算法(递归的方式): 创建一个查找算法,参数列表有left,right,findValue,array创建一个变量mid,通过left和right获取mid通过对mid的比较,决定递归方向最后判断是否能找到 请注意所有的二分查找算法都是建立在数组有序的基础上的,如果带查找序列是无序序列,不能用二分查找算法,只能使用其他查找算法,谨记! 经典写法(找单值): 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,mid1,right,findValue);}else if(findValue midValue) {return binarySearchSingle(array,left,mid-1,findValue);}else {return mid;}} 代码分析: left是左索引,right是右索引,应该一开始就被赋值为0与array.length-1(因为带查找的值在他们两个索引之间,即[left,right]区间内有带查找元素)findValue是待查找的值,array是带查找的数组二分查找法顾名思义是折半,所以mid 1/2(left right) left 1/2*(right - left) 注意:后面的表达式非常的重要,是折半查找发的关键 将mid下标对应的值放入midValue 情况: 如果midValue大于findValue,由于有序,说明待查找的元素在mid右边且不为mid,所以得出了[mid1,right]的范围内有带查找元素,故left mid1如果midVvalue小于findValue,由于有序,说明带查找的元素在mid左边且不为mid,所以得出了[left,mid-1]的范围内有带查找元素,故right mid-1如果midValue findValue,说明找到了该元素,直接返回mid即可,mid是下标如果left right,由于没有这样的区间(即区间左边必须小于右边的值),说明找不到,直接返回-1如果findValue大于列表的最后一个值,由于有序,最后一个值为最大值,说明列表里面不可能有与findValue相同的值,直接返回-1 经典写法(找数组即多个返回值) public static ListInteger binarySearchMore(int[] array,int left,int right,int findValue) {if(left right || findValue array[length-1]) {return new ArrayListInteger();}var mid (left right)/2;var midValue array[mid];if(findValue midValue) {return binarySearchMore(array,mid1,right,findValue);}else if(findValue midValue) {return binarySearchMore(array,left,mid-1,findValue);}else {var list new ArrayListInteger();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;} 代码分析 注意:由于其他代码都一样,我们重点分析一下else里面的代码当程序进入else时,说明找到了该元素,由于我们要实现多元素返回,我们可以借助集合,故我们要new一个ArrayLsitInteger先将该元素add进去集合中创建一个辅助索引temp,赋值为mid-1(目的:向左遍历)通过while循环,如果temp0(防止数组下标越界异常),且array[temp] findValue,说明此元素也是我们要找的元素,添加入集合中如果while布尔表达式为false,说明temp遍历到了最左边或是不相等,由于列表的有序性,如果不相等,则前面的元素一定比midValue小,不可能再有带查找的元素,直接结束向左遍历temp赋值为mid1(目的:向右遍历)同理5~6最后返回list即可特别注意的是,如果找不到,我们返回一个空的集合,所以在最前面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. 0n-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. 寻找两个正序数组的中位数困难题解 参考资料 二分查找从入门到入睡 - 力扣LeetCode代码随想录704. 二分查找 - 力扣LeetCode
