LeetCode每日练习 | 二分查找 | 数组 |Java | 图解算法

🙋大家好！我是毛毛张!
🌈个人首页： 神马都会亿点点的毛毛张

📌 你真的刷明白了二分查找吗⁉️记得看毛毛张每个题目中写的【注意细节】⚠️

---

---

0.前言🍁

• 📌毛毛张在刷算法题的时候有两个感悟：
  • 1️⃣有很多算法题的难点在于对于特殊情况的判断，很多时候我们实现的算法能通过大部分的测试案例，但是对于一些特殊案例不能通过，这可能是因为逻辑本来就错误，那么我们的算法需要重新设计考虑，另一种原因是因为算法对于一些边界问题没有考虑进去，那么我们需要对于算法的一些特殊情况的判断要考虑进去
  • 2️⃣很多算法题刷到后面就是数学题，如果能有比较好的数学基础，对于求解一些算法题是有帮助的，但是对于大多数人来说，数学都不是很好，包括毛毛张在内，所以毛毛张在刷算法题的时候很少直接使用数学方法来求解题目，毛毛张在介绍的时候也希望通过简单的逻辑思考而不需要很高深的数学问题来求解算法，这样才能让每个人都学习算法，而不是觉得算法很难，不能接受
• 📌今天毛毛张要分享的代码随想录中的第一个题目：二分查找，这个在查找算法中一个比较简单的算法，并且在LeetCode也是一道比较简单的题目，但是里面却有很多需要注意的细节

1.704. 二分查找🍍

LeetCode标签：简单

1.1 题目描述🥥

给定一个 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

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

1.2 题解🍈

• 二分查找是利用数组的有序性，每轮缩窄一半的查找区间（即排除一半元素），直到找到目标值或查找区间为空时返回的查找算法
• 时间复杂度： 由于每轮可以排除一半元素，因此查找最多循环 $lo{g}_{2}N$ 次，所以时间复杂度 $O(lo{g}_{2}N)$
  • 在数据量较大时，二分查找的效率大幅高于线性查找 $O(N)$
• 我们通过下面算法流程来理解二分查找法的缩窄区间的含义：给定升序数组nums和目标值target，二分查找流程如下
  • 第一步：定义查找区间，初始化双指针min、max分别指向数组首、尾元素，代表查找区间为闭区间[min,max]；
  • 第二步：循环二分，缩窄查找区间：
    • 使用向下取整除法，计算区间$[min,max]$的中点mid；
    • 若$nums[mid]<target$ ，根据数组有序性，易得$target$一定不在闭区间$[min,mid]$中，因此执行$min=mid+1$ ，即将查找区间缩窄至 $[mid+1,max]$；
    • 若$nums[mid]>target$， 根据数组有序性，易得$target$一定不在闭区间$[mid,max]$中，因此执行$max=mid-1$，即将查找区间缩窄至$[min,mid-1]$；
    • 若$nums[mid]=target$ ，说明找到$target$，返回索引$mid$即可；
  • 不满足$min\le max$时跳出循环，此时代表无法在数组中找到目标值target，因此返回$-1$
• 上面的二分查找的流程非常详细，然鹅在具体的代码实现过程中，根据二分查找区间的开闭情况又可以分为两种写法：
  • 如果二分查找区间均为闭区间[min,max]，则循环结束判断条件为while(min <= max)，对应下面写法1
  • 如果二分查找区间均为左闭右开区间[min,max)，则循环结束判断条件为while(min < max)，对应下面写法2
• 上面的理论分析和分类说明比较枯燥，大家可以看下面的图解和代码实现

1.2.1 二分查找写法1

算法图解：



算法实现：

class Solution {
    public int search(int[] nums, int target) {
        // 左边索引
        int min = 0;
        // 右边索引
        int max = nums.length - 1;

        // 开始二分查找逻辑
        while (min <= max) {
            // 中间索引
            int mid = (max - min) / 2 + min;
            // 获取中间值，并进行比较
            if (nums[mid] == target) {
                return mid;
            } else if (target > nums[mid]) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }

        return -1;
    }
}

1.2.2 二分查找写法2

算法图解：


算法实现：

class Solution {
    public int search(int[] nums, int target) {
        // 左边索引
        int min = 0;
        // 右边索引
        int max = nums.length;

        // 开始二分查找逻辑
        while (min < max) {
            // 中间索引
            int mid = (max - min) / 2 + min;
            // 获取中间值，并进行比较
            if (nums[mid] == target) {
                return mid;
            } else if (target > nums[mid]) {
                min = mid + 1;
            } else {
                max = mid;
            }
        }

        return -1;
    }
}

1.3 注意细节⚠️

• 这个题目的是二分查找的入门题目，比较简单，但是有两个细节需要注意：
• 细节1： 就是前面说到的根据查找区间的开闭情况不同，结束循环的条件也应该不同
• 细节2： 计算中间索引所用的公式，有以下两种写法
  • 写法1：int mid = (max + min) / 2;，但是可能会导致溢出，如果 max 和 min 都是非常大的正数或负数，max + min 的值可能会超过 int 类型的范围。
  • 写法2：int mid = (max - min) / 2 + min;，避免了溢出问题，因为 max - min 不会超过 max 或 min 的范围。
  • 代码说明：

    max = Integer.MAX_VALUE;
    min = Integer.MAX_VALUE - 1;
    int mid = (max - min) / 2 + min;  // 结果为 Integer.MAX_VALUE - 1
    int mid = (max + min) / 2;  // 结果可能导致溢出，变为负数
    

• 根据毛毛张在上面的写法中可以看出，对于计算中间值mid，毛毛张跟倾向于下面的写法，虽然在此题中不会出现溢出的情况，但是在别的题目中就可能会出现，例如下面的相关题目！

---

2.35. 搜索插入位置🍎

LeetCode标签：简单

2.1 题目描述🍏

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• $1<=nums.length<=10^4$
• $-10^4<=nums[i]<=10^4$
• nums 为 无重复元素 的 升序 排列数组
• $-10^4<=target<=10^4$

2.2 题解🥦

• 这很明显是一道查找的题目，并且要求时间复杂度为 O(log n) 的算法，于是很容易想到采用二分查找。
• 与上面第一道题目的不同之处在于，第一道题目关注的是否找得到，此题还需要关注找不到时插入的位置，因此，我们需要关注退出循环之后的min和max的值代表什么？ 清楚知道这一点是求解本题的关键，同样根据二分查找区间的开闭情况分为两种写法
• 在做题之前我们还需要考虑到这个题目插入的四种情况：
  • 目标值在数组所有元素之前
  • 目标值等于数组中某一个元素
  • 目标值插入数组中的位置
  • 目标值在数组所有元素之后
    
• 这道题目要求算法实现复杂度为$O(log(N))$，但是也不要忘记了最简单质朴的解法，所以毛毛张在这里首先还是要介绍一下暴力解法

2.2.1 暴力求解

class Solution {
    public int searchInsert(int[] nums, int target) {
        //暴力解法
        int i;
        for(i = 0;i < nums.length;i++){
            // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果
            if(nums[i] >= target) break; 
        }
        //如果target大于整个数组，那么循环结束后 i = nums.length
        return i;
    }
}

2.2.2 二分查找写法1

class Solution {
    public int searchInsert(int[] nums, int target) {
        //二分查找
        int left = 0;
        int right = nums.length;
        while(left < right){// 因为left == right的时候，在[left, right)是无效的空间
            int mid = (left + right) / 2;
            if(target == nums[mid]) return mid;// 数组中找到目标值的情况，直接返回下标
            else if(target > nums[mid]){
                left = mid + 1;// target 在右区间，在 [mid+1, right)中
            }else{
                right = mid;// target 在左区间，在[left, mid)中
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前 [0,0)
        // 目标值等于数组中某一个元素 return mid
        // 目标值插入数组中的位置 [left, right) ，return right 即可
        // 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right
        return right;
    }
}

2.2.3 二分查找写法2

class Solution {
    public int searchInsert(int[] nums, int target) {
        //二分查找
        int left = 0;
        int right = nums.length - 1;// 定义target在左闭右闭的区间里，[left, right]
        while(left <= right){// 当left==right，区间[left, right]依然有效
            int mid = (left + right) / 2;
            if(target == nums[mid]) return mid;// nums[mid] == target
            else if(target > nums[mid]){
                left = mid + 1;// target 在右区间，所以[mid + 1, right]
            }else{
                right = mid - 1;// target 在左区间，所以[left, mid - 1]
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return mid;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
        return right + 1;
    }
}

---

3.69. x 的平方根 🍊

LeetCode标签：简单

3.1 题目描述🌽

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• $0<=x<=2^{31}-1$

3.2 题解🍓

• 有人说算法的本质就是数学，这道题目本质就是一道数学题目：如何求得一个非负整数的算数平方根的整数部分

• 在数学上有两种方法来求解这道题目：二分查找和牛顿迭代法，这两种方法的本质就是通过公式不断迭代来逼近目标值

• 二分查找： 由于x平方根的整数部分mid是满足$k^2\le x$的最大$k$值，因此我们可以对 k 进行二分查找，从而得到答案。

  • 二分查找的下界为 0，上界可以粗略地设定为x。
  • 在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。
  • 由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 mid 后，也就不需要再去尝试 mid+1了

• 二分查找图解：
  

• 牛顿迭代法： 说实话这个题目用牛顿法来进行求解就是纯纯的数学题了，涉及到数学上面的推导，做起来还是比较复杂的，如果感兴趣的同学可以参考LeetCode上面的数学推导：牛顿迭代法数学推导，由于这是数学中的一个比较常见的问题，毛毛张在这里直接附上使用牛顿迭代法的计算公式：

  • 如果要求$S\left(S>1\right)$的平方根，选取$1<x_0<S$，其迭代公式为：$x_{n+1}=\frac{1}{2}\left(x_n+\frac{S}{x_n}\right)$

• 牛顿迭代法举例： 求$\sqrt{125348}$的算是平方根
  )

• 同样大家不要忘记了如何使用内置函数和暴力方法进行求解，让我们先看一下最基础的解法是怎么样的，然后再来看二分查找和牛顿迭代法

3.2.1 使用内置函数

class Solution {
    public int mySqrt(int x) {
        return (int)Math.sqrt(x);
    }
}

3.2.2 暴力解法

class Solution {
    public int mySqrt(int x) {
        //暴力解法
        long i =0,square = 0;
        while(square <= x){
            i++;
            square = i * i;
        }
        return (int) i-1;
    }
}

3.2.3 二分查找法

class Solution {
    public int mySqrt(int x) {
        //二分查找法
        int left = 0;
        int right = x;
        while(left <= right){
            int mid = left + (right - left) / 2;
            long square = (long) mid * mid;
            if(square > x){
                right = mid - 1;
            }else if(square < x){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return right;
    }
}

3.2.4 牛顿迭代法

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

3.3 练习：367. 有效的完全平方数🍒

LeetCode标签：简单

3.3.1 题目描述🍇

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

• $0<=x<=2^{31}-1$

3.3.2 题解

• 这道练习和上面一道题目类似，毛毛张就不做过多介绍了，大家根据上面的的方法来进行求解，并且这道题目比上面的一道题目还要简单一些

3.3.2.1 使用内置函数

class Solution {
    public boolean isPerfectSquare(int num) {
        //对目标值直接进行开根号，并强制转化为整数
        int a = (int) Math.sqrt(num);
        return a * a == num ? true : false;
    }
}

3.3.2.2 暴力解法

class Solution {
    public boolean isPerfectSquare(int num) {
        //暴力解法
        long i = 1,square = 1;
        while(square <= num){
            if(square == num) return true;
            i++;
            square = i * i;
        }
        return false;
    }
}

3.3.2.3 二分查找法

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num ;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            //注意，此处求平方一定要进行转换成更大的类型
            long square = (long) mid * mid;
            if(square > num){
                right = mid - 1;
            }else if(square < num){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }
}

3.3.2.4 牛顿迭代法

class Solution {
    public boolean isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
}

3.4 注意细节⚠️

• 这道题目在计算的过程中就可能会遇到数据溢出的情况，需要注意，一个地方是二分法中，计算mid值的时候，另一个地方是在计算平方的时候

  int mid = (right - left) / 2 + left;
  //注意，此处求平方一定要进行转换成更大的类型
  long square = (long) mid * mid;
  

---

4.34. 在排序数组中查找元素的第一个和最后一个位置🍌

LeetCode标签：中等

4.1 题目描述🍍

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• $0<=nums.length<=10^5$
• $-10^9<=nums[i]<=10^9$
• nums 是一个非递减数组
• $-10^9<=target<=10^9$

4.2 题解🥭

• 很简单的思路就是先找到符合条件的元素，在分别向左边和右边进行搜索，这样就有了我们的暴力解法，但是这样求解的时间负责度和直接从左到右进行查找的时间复杂度本质是相同的，均为$O(n)$

• 这道题目要求时间复杂度为 $O(logn)$，因此我们就需要使用二分查找法来进行解决， 这道题目也是充分考虑二分查找的特性的题目，第二题使用二分查找法是充分利用循环结束后查找区间的端点值[min,max]，这道题目既要利用这一特性，同时还需要在二分查找的判断语句上下功夫

• 二分法寻找左边界：

  if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
  right = middle - 1;
  leftBorder = right;
  } else {
  left = middle + 1;
  }
  

• 二分法寻找右边界：

  if (nums[middle] > target) {
  right = middle - 1;
  } else { // 寻找右边界，nums[middle] == target的时候更新left
  left = middle + 1;
  rightBorder = left;
  }
  

4.2.1 暴力解法

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 创建结果返回值
        int[] result = { -1, -1 };
        // 判断特殊情况
        if (nums == null || nums.length == 0)
            return result;

        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                int l = mid, r = mid;
                // 获取左端点索引
                while ((l - 1) >= 0 && nums[l - 1] == nums[l]) {
                    l--;
                }
                // 获取右端点索引
                while ((r + 1) <= (nums.length - 1) && nums[r + 1] == nums[r]) {
                    r++;
                }

                result[0] = l;
                result[1] = r;
                return result;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

• 这个解法看似使用了二分法，但是其时间复杂度还是$O(n)$，还不如直接for循环进行求解

4.2.2 二分查找写法1

class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2)
            return new int[] { -1, -1 };
        // 情况三
        if (rightBorder - leftBorder > 1)
            return new int[] { leftBorder + 1, rightBorder - 1 };
        // 情况二
        return new int[] { -1, -1 };
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}

• 上面的写法比较复杂，因此我们在先如何将上面的寻找左边界和右边界进行统一，于是我们可以在二分查找的函数中加上一个标志位，这样就能把两种方式进行统一，于是就有了下面的写法2

4.2.3 二分查找写法2

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //左边界
        int leftIdx = binarySearch(nums,target,false);
        int rightIdx = binarySearch(nums,target,true) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    //二分查找
    public int binarySearch(int[] nums,int target,boolean flag){
        //flag用来标志查找左边界还是右边界
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(target > nums[mid] || (flag && target >= nums[mid])){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
}

5.总结🌍

• 相信通过上面四道题目+一道练习，大家可以算是对二分法的特性有了初步的了解，但是，上面的几道题目仅仅二分法中比较简单的题目
• 如果想练习更多二分法的题目可以点击此处进行跳转：宫水三叶二分法类型题解
  

---

---

参考文献🎁

• LeetCode官网
• 代码随想录

原文地址：https://blog.csdn.net/weixin_48235955/article/details/140673375

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！