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

二分算法刷题

1. 初识

总结:二分算法题的细节非常多,容易写出死循环。使用算法的条件不一定是数组有序,而是具有“二断性”;模板三种后面会讲。

  • 朴素二分
  • 二分查找左端点
  • 二分查找右端点

2. 朴素二分

题目链接:704. 二分查找 - 力扣(LeetCode)

循序渐进,先从暴力解法说起。

  1. 暴力解法:遍历全部数组,判断是否==target。时间复杂度O(n)。但是这里没有把数组是有序的这个条件给用上。
  2. 二分查找算法:

“二段性”,当我们发现:我们发现一个规律,在选择一个状态的时候,能够直接丢弃掉“一半”的情况。

只要选取的位置能够将全部情况划分为两个情况就可以,可以是二分之一点,要和可以是三分之一点。

但是从概率上来讲,还是每次选取二分之一点的效率最好。

编写代码

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

朴素二分模板

朴素二分求mid的时候使用( left + right)/ 2 还是使用(left + right + 1)/2都是一样的

3. 在排序数组中查找元素的第一个位置和最后一个位置。(查找区间左端点、右端点)

题目链接:34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

3.1. 暴力解法

遍历查找,第一次遇到这target标记下标,然后继续往后遍历,直到第一次找到大于target的下标。

3.2. 二分

暴力算法同样没有使用数组是有序的这个重要条件。

先来看看朴素二分能不能解决问题?

是不能的,朴素二分只能保证找到target,但是并不能保证找到的index就是边界啊。

因此就引出了另外两种二分:查找左端点、查找右端点的二分。

3.2.1. 查找左端点

朴素二分是将数组划分成3个状态(大于的、小于的、等于的)。

而查找左端点的时候是不可以将数组划分为三个状态的,这是因为的等于状态的位置请不确定,需要将其和大于状态划分到一起,这个等于的点,有可能刚好就是我们要找的左端点。

这样划分之后,

如果mid落在了【小于target】的这一段区间中,我们的mid该怎么更新状态呢?由于这里已经小于了target,而我们的目标是找到target的左端点,所以mid = mid+1.

如果mid落在了【大于等于target】这一段的区间中,mid则 mid = right,这是因为right很有可能就是我们想要寻找的左端点,不可以跳过。

那么循环的条件是什么?

无论是【】区间中有结果,还是区间中所有的数字都大于target,或者是小于target,最终,当最终left和right重合的时候,都不需要到循环中再次判断了,这就是最终状态,只需要判断这个时候的left是不是等于target即可。

如果当left==right时候,在进入循环就会陷入死循环。

求mid的操作是什么?

这里是求左端点,所以mid = (right - left )/ 2;或者 mid = left + (right-left) /2;

如果使用 mid = left +(right - left + 1) / 2;也会死循环

3.2.2. 查找右端点

原理同上。注意二段性的运用

3.2.3. 代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1 ,-1};
        int[] ret = new int[2];
        int left = findLeft(nums,target);
        int right = findRight(nums,target);
        ret[0] = left; ret[1] = right;
        return ret;

    }

    private static int findLeft(int[] nums , int target){
        int left = 0 , right = nums.length - 1;
        int mid = 0;
        while(left < right){
            mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] != target) return  -1;
        else return left;
    }

    private static int findRight(int[] nums , int target){
        int left = 0 , right = nums.length - 1;
        int mid = 0;
        while(left < right){
            mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid ;
            else right = mid -1;
        }
        if(nums[left] != target) return  -1;
        else return right;
    }
} 

3.2.4. 模板

不要死记硬背!理解

记住:就中间坐标的方式,其他的可以关联记忆!(分析二段性 --> 分析求中点mid应该怎么求(当下面出现剑法,求mid就有+1;反之则反)),具体的分类讨论的代码,就题论题。分析好中点落在某个区间的时候,left、以及right如何变化。

4. x的平方根

题目链接:69. x 的平方根 - 力扣(LeetCode)

4.1. 暴力解法

从1开始,一次遍历,计算i*i 和 x的大小。

这个大小具体满足什么要求?来看题目,题目要求返回的是整数,小数部分就会被舍去。也就是找到最大的i,满足i*i <= x.

4.2. 二分

暴力解法中其实已经看到了 二段性,在计算i*i的时候,如果不能满足要求,就可以直接排除掉“另一半”的数据量。从上面的分析也可以很清楚的看到,我们需要寻找的就是“满足条件”的数据的右端点。也就是找到 找到最大的i,满足i*i <= x.

进入循环的条件:while(left < right)

求mid的方式 : mid = left + (right -left + 1)/ 2;

开始二分

if (i*i <= x)left = mid;(因为求的是 右端点,这里有可能是等于的情况,也就是右端点,因此不可以left = mid + 1).

if (i*I > x) right = mid -1; (这里已经大于了,不可能包含我们需要的数据)

代码

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        long left = 1, right = x;
        long mid;
        while(left < right){
            mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid -1;
        }
        return (int)left;

    }
}

5. 搜索插入顺序

题目链接:

35. 搜索插入位置 - 力扣(LeetCode)

5.1. 暴力解法

遍历数组,找到第一个等会或者大于target的数字,返回其下标。

5.2. 二分

实际上就是适用二分法求取区间的左端点,该区间是大于等于target的这个区间。

进入循环的条件 while(left< right)

求mid = left+(right - left) / 2;

if(nums[i] < target)left = mid+1; 该区间没有满足的情况,直接跳出;

if(nums[i] >= target) right = mid; 该区间有可能,存在【左端点】,也就是恰好nums[i] == target.

结束循环后。left=right,需要判断这时候是存在nums[left] == target,还是不存在,需要返回插入的下标(此时,nunms[left] < target,返回left+1)

代码:

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

    }
}

6. 山脉数组的峰值

题目链接:852. 山脉数组的峰顶索引 - 力扣(LeetCode)

6.1. 暴力解法

遍历数组中的元素,逐一判断该值是否是【峰值】,峰值的话就是大于前驱,同时也大于后继。

6.2. 二分

这道题目的难点在于,如何能看出来使用二分。

前面说过,二分的题目是看数据的二段性,这道题目的二段性在哪里?

class Solution {
    public int peakIndexInMountainArray(int[] arr) {

        int left =  0, right = arr.length - 1;
        while(left < right){
            int mid = left + (right - left ) / 2;
            if(arr[mid] < arr[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;

    }
}

7. 搜索旋转排序数组中的最小值

题目链接:153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

7.1. 暴力解法

遍历数组,通过比较记录数组中的最小元素,得到的就是最小值。

此时,并没有使用到数组的特殊性质,该数组使用过升序数组“旋转”得到的。

7.2. 二分

为什么能使用二分?

代码:

public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 如果中间元素大于右边界元素,说明最小值在右半部分
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                // 否则,最小值在左半部分或是mid本身
                right = mid;
            }
        }
        
        return nums[left];

    }

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

相关文章:

  • 【uni-app运行错误】SassError: expected selector @import “@/uni.scss“;
  • 11 Collection集合、Map集合:分类、功能、遍历、底层原理,Stream流:获取、中间方法、终结方法 (黑马Java视频笔记)
  • 探索 Rust 高效 Web 开发:Hyperlane 框架深度解析
  • Spring Boot 参数校验异常与错误编码映射方案
  • 线性回归中的最小二乘法:直接法与梯度下降的比较
  • Android 高版本兼容的原生定位工具类封装(支持 Android 5.0 到 Android 14)
  • kotlin中的模块化结构组件
  • 机器人交社保属于“无稽之谈”?
  • 《Operating System Concepts》阅读笔记:p309-p330
  • uni-app 生命周期
  • 数学建模 第二节
  • 深度学习模型压缩:非结构化剪枝与结构化剪枝的定义与对比
  • 基于C#的以太网通讯实现:TcpClient异步通讯详解
  • 政策助力,3C 数码行业数字化起航
  • 考研408-数据结构完整代码 线性表的顺序存储结构 - 顺序表
  • 运维工具推荐 -- 宝塔面板:一键部署服务器
  • nexus的使用
  • Linux搭建conda虚拟环境流程
  • never_give_up
  • 聊一下CSS层叠