当前位置： 首页 > article >正文

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

article 2025/1/24 8:56:09

目录

前言

什么是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左侧元素「必」小于target
            else 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左侧元素「必」小于target
            else 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左侧元素「必」小于等于target
            else 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左侧「必」小于等于target
            else 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左侧元素「必」小于target
            else 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及其左侧元素「必」小于target
            else 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及其左侧元素「必」小于等于target
            else 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及其左侧元素「必」小于target
            else 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及其左侧元素「必」小于target
            else 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）


http://www.kler.cn/a/516083.html

相关文章：

  • 从零到一：Spring Boot 与 RocketMQ 的完美集成指南
  • k8s使用nfs持久卷
  • java.sql.Date 弃用分析与替代方案
  • 图谱之前端关系应用
  • 2000-2010年各省第三产业就业人数数据
  • 数据结构：二叉树
  • 洛谷刷题1-3
  • Java如何实现反转义
  • 【Ubuntu】安装SSH启用远程连接
  • UE 像素流Pixel Streaming笔记
  • 五种高频设计模式及其在 Spring 中的应用揭秘
  • Git克隆 提示证书验证失败解决
  • Python OrderedDict 实现 Least Recently used（LRU）缓存
  • 【易康eCognition实验教程】002：创建工作空间、工程
  • 分布式光纤应变监测是一种高精度、分布式的监测技术
  • element tbas增加下拉框
  • Windows Server 虚拟化环境中SR-IOV网络I/O增强功能
  • HTML5 常用事件详解
  • JavaScript图像处理，常用图像边缘检测算法简单介绍说明
  • 51 单片机矩阵键盘密码锁：原理、实现与应用
  • 微信小程序中实现进入页面时数字跳动效果(自定义animate-numbers组件)
  • 前后端交互过程
  • mysql my.ini 配置参数结束
  • 高性能队列 Disruptor 在 IM 系统中的实战
  • Linux进程间通信（补充）
  • 用 Java 发送 HTML 内容并带附件的电子邮件