算法——二分查找

二分算法简介:

  1. 二分查找算法只适用于数组有序的情况?(只要数组中存在某种规律就可以用)
  2. 模版:
    1. 朴素的二分模版
    2. 查找左边界的二分模版
    3. 查找右边界的二分模版

朴素二分模版


while(left <= right)
    {
        int mid = left+ (right-left+1)/2 ;  //防止溢出
        if(...) 
            left = mid+1;
        else if(...) 
            right = mid-1;
        else 
            return ...;
    }

查找区间左端点/右端点的二分模版

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

二分查找

二分查找

题目解析

  • n个元素有序的数组,找到 target并返回数组下标

算法原理

  1. 暴力解法:从头到尾遍历,若找到目标值返回下标,否则返回-1。时间复杂度O(n),但并没有利用数组的有序性

  2. 一个数组中,随机找一个数,去和target进行比较,做完比较之后,划分出两个区域;其中根据规律可以有选择性的舍去一个规律,继续在另一个规律中寻找。此时该题目具有二段性,我们可以用二分查找算法(这里选取二分之一是最优选择,因为他的时间复杂度以及根据概率学问题是最优的)image.png

  3. 朴素二分查找算法:我们来探讨一下细节问题

image.png

  1. 循环结束的条件:left>right

  2. 为什么是正确的:因为我们是从暴力解法优化而来的,相较于法一的逐个淘汰,二分查找可以帮我们一次性淘汰一段区间的数字

  3. 时间复杂度:

    image.png

代码实现

class Solution {
public:
int search(vector<int>& nums, int target) {
    int left = 0,right = nums.size()-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;
}
};

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

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

题目解析

  • 该数组为非递减序列的数组,返回目标值开始和结束的位置。如果不存在返回-1(注:题中示例三,如果是空数组,为了避免造成越界访问,我们要特殊处理,直接返回-1)image.png

算法原理

  1. 暴力解法:从前往后遍历数组一遍,此时时间复杂度O(n)。
  2. 朴素二分:虽然可以找到目标值,但是不确定该值是否是起始位置或者终点位置,可能还需要向前遍历和向后遍历寻找,所以极端情况下他的时间复杂度为O(n)

image.png

  1. 优化朴素二分
寻找左边界
  1. 寻找左边界:retLeft 表⽰左边界, retRight 表⽰右边界
    我们注意到以左边界划分的两个区间的特点:

    1. 左边区间[left, retLeft - 1] 都是⼩于 x 的;
    2. 右边区间(包括左边界) [retLeft, right] 都是⼤于等于 x 的;
  2. 因此,关于mid的落点,我们可以分为下⾯两种情况:

    1. 当我们的 mid 落在 [left, retLeft - 1] 区间的时候,也就是 arr[mid] <target 。说明 [left, mid] 都是可以舍去的,此时更新left 到 mid + 1 的位置,继续在 [mid + 1, right] 上寻找左边界;

    2. 当mid落在 [retLeft, right] 的区间的时候,也就是 arr[mid] >= target 。说明 [mid + 1, right] (因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时更新 right 到 mid 的位置,继续在 [left, mid] 上寻找左边界

      细节处理:

  3. 循环条件:这里要写成left<right 。情况分析中,left和right的最终归宿都是走到一起(1.left和right一起向中间靠拢。2.left疯狂向右移动 3.right疯狂向左移动)

    1. 这里说一下会死循环的原因:当判断等号的情况时,right+left会进入第二个条件,但right位置不变,mid依旧是这个位置,下次进入判断循环条件时会继续进入第二个,此时进入死循环。
  4. 求中点操作:若用第二个,则mid会落在right的位置上,此时如果进入第一个循环条件没问题,但是进入第二个循环条件,right位置没有动,求出的mid还是这个位置,下次进入循环条件时还是进入第二个,所以会进入死循环

注意:这⾥找中间元素需要向下取整。因为后续移动左右指针的时候:

  • 左指针: left = mid + 1 ,是会向后移动的,因此区间是会缩⼩的;
  • 右指针: right = mid ,可能会原地踏步(⽐如:如果向上取整的话,如果剩下 1,2 两个元素, left == 1 , right == 2 , mid == 2 。更新区间之后, left,right,mid 的值没有改变,就会陷⼊死循环)。因此⼀定要注意,当 right = mid 的时候,要向下取整。

image.png

寻找右边界

我们注意到右边界的特点:

  1. 左边区间(包括右边界) [left, retRight] 都是⼩于等于 x 的;右边区间 [retRight+ 1, right] 都是⼤于 x 的;因此,关于 mid 的落点,我们可以分为下⾯两种情况:
    1. 当我们的 mid 落在 [left, retRight] 区间的时候,说明 [left, mid - 1]( mid 不可以舍去,因为有可能是最终结果)都是可以舍去的,此时更新 left 到 mid 的位置;
    2. 当 mid 落在 [retRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素是可以舍去的,此时更新 right 到 mid - 1 的位置;
    3. 由此,就可以通过⼆分,来快速寻找右边界;
  2. 注意:这⾥找中间元素需要向上取整。因为后续移动左右指针的时候:
    1. 左指针: left = mid ,可能会原地踏步(⽐如:如果向下取整的话,如果剩下 1,2 两个元素, left == 1, right == 2,mid == 1 。更新区间之后, left,right,mid 的值没有改变,就会陷⼊死循环)。
    2. 右指针: right = mid - 1 ,是会向前移动的,因此区间是会缩⼩的;因此⼀定要注意,当right = mid 的时候,要向下取整。

image.png

代码实现

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        // 处理边界情况
        if(nums.size() == 0) return {-1, -1};
        int begin = 0;
        // 1. ⼆分左端点
        int left = 0, right = nums.size() - 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 {-1, -1};
        else begin = left; // 标记⼀下左端点
        
        // 2. ⼆分右端点
        left = 0, right = nums.size() - 1;
        while(left < right)
        {
        int mid = left + (right - left + 1) / 2;
        if(nums[mid] <= target) left = mid;
        else right = mid - 1;
        }
        
    return {begin, right};
    }
};

X的平方根

x的平方根

题目解析

  • 返回类型是整数类型,只保留整数部分
  • 不允许使用任何内置指数函数和算符

算法原理

  1. 暴力解法:从1开始遍历一个一个试。
  2. 二分查找:设ret是x的平方根,最终结果用ret表示,则ret左边的是平方后小于等于x的,右边是大于x的。这时出现二段性,使用二分查找
    1. 在left移动时,因为left有可能是最终结果(ret左边部分是小于等于的情况),所以不能直接越过mid,所以不能写成mid+1。所以用查找区间右端点的模板

image.png

代码实现

class Solution {
public:
    int mySqrt(int x)
    {
    if(x < 1) return 0; // 处理边界情况
    int left = 1, right = x;
    while(left < right)
    {
        long long mid = left + (right - left + 1) / 2; // 防溢出
        if(mid * mid <= x) left = mid;
        else right = mid - 1;
    }
        return left;
    }
}; 

搜索插入位置

搜索插入位置

题目解析

  1. 如果能找到,返回数字下标
  2. 如果找不到,返回该数字应该按照顺序插入的位置下标
  3. 请必须使用时间复杂度为 O(logn) 的算法。

算法原理

二分查找:

  1. 插入位置有数:找到,直接返回下标
  2. 插入位置没数:寻找出现第一个比该数大的位置,或者是数组最后一个位置

综上所述,插入位置ret最终应该大于等于目标值,因此通过ret将数组划分为两个区间,此时发现二段性,用二分查找。所以我们只需要找到大于等于目标值区间的左端点即可。所以我们套用查找区间左端点的模板

当x<t时,最终结果一定不会在左边这个区间,所以直接让left=mid+1(可以跳过),当x>=t时,right可能是最终结果,所以不能越过mid。
image.png

代码实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) left = mid + 1;
        else right = mid;
        }
        //此时right和left已经相遇,所以这里返回谁都可以
        if(nums[left] < target) return right + 1; //插入位置在数组最后一个位置
        return right;
    }
};

山脉数组的峰顶索引

山脉数组的峰顶索引

题目解析

  • 寻找峰值的下标,该题是严格存在山峰数组,只有一个山峰

image.png

算法原理

  1. 暴力解法:从第一个开始遍历,当该数字小于前一个数字,则不是峰值,当第一个出现大于前一个数的,则是峰值。时间复杂度O(n)
  2. 优化探寻性质:红色箭头一侧的性质:后一个数字总是大于前一个数字;蓝色箭头一侧的性质:后一个数总是小于前一个数。所以发现二段性,用二分查找(这里我们得出即使数组没有单调性,也可以二分查找)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

  1. 当数字落在红色箭头这一列时,峰值是在这一区间的右端点,所以不能跳过,故更新left位置时,left=mid;

  2. 当数字落在蓝色箭头这一列时,峰值一定不会在该区域,所以更新right位置时,right = mid-1;

     	![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2Fcdn.nlark.com%2Fyuque%2F0%2F2023%2Fpng%2F29339358%2F1701759796953-a2869478-00eb-45f8-8a7a-6bdc4f7be763.png%23averageHue%3D%2523fefefe%26clientId%3Due138c47e-15f4-4%26from%3Dpaste%26height%3D431%26id%3Dud9b4daa7%26originHeight%3D539%26originWidth%3D716%26originalType%3Dbinary%26ratio%3D1.25%26rotation%3D0%26showTitle%3Dfalse%26size%3D124540%26status%3Ddone%26style%3Dnone%26taskId%3Du823856d0-63c3-47fb-9831-9f68416db8b%26title%3D%26width%3D572.8&pos_id=img-eMGVQ748-1701766742087)
    

代码实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1,right = arr.size()-2; //这里不让left=1,right=arr.size()-1是因为不可能在第一个位置
        while(left < right)
        {
            int mid = left+(right-left+1)/2;
            if(arr[mid] > arr[mid-1]) left = mid;
            else right = mid-1;
        }
        return left;

    }
};

寻找峰值

寻找峰值

该题严格无序数组,可能出现多个山峰的情况

题目解析

  • 峰值元素是大于左右相邻两个数;峰值可能有多个,返回任意一个位置的下标即可
  • 数组中不会有相邻的相同元素,对于所有有效的 i 都有 nums[i] != nums[i + 1]

算法原理

  1. 暴力解法:会遇到三种情形:(时间复杂度O(n))
    1. 从第一个位置开始走,发现直接开始下降,则第一个位置就是峰值
    2. 从第一个位置开始,现逐渐上升,后下降,返回下降前的峰值
    3. 从第一个位置开始,发现一直上升,则返回最后一个位置的下标image.png
  2. 优化:总体分为两种情况
    1. 当arr[i] > arr[i+1](红色箭头),此时左区间一定会存在峰值,右区间可能会存在
    2. 当arr[i] < arr[i+1](蓝色箭头),此时右区间一定会存在峰值,左区间可能会存在

image.png

故得出二段性,使用二分查找。

  1. 当arr[i] > arr[i+1],此时左区间一定有结果(上图,左区间包含i),则让right去到左区间,故right = mid;
  2. 当arr[i] < arr[i+1],此时右区间一定有结果(右区间包含i+1),则让left去到右区间,故right = mid+1;

image.png

代码实现

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0,right = nums.size()-1;
        while(left < right)
        {
            int mid = left+(right-left)/2;
            if(nums[mid] > nums[mid+1]) right = mid;
            else left = mid+1;
        }
        return left;

    }
};

寻找旋转排序数组中的最小值

寻找旋转排序数组中的最小值

题目解析

  • 旋转操作:将最后一个数放到最前面
  • 找出数组的最小值,返回该元素

算法原理

  1. 解法一:暴力解法:遍历查找最小值,时间复杂度为O(n)

  2. 解法二:二分查找:可以把旋转后的数组分为两部分,两部分都是呈现递增的形式,把该问题抽象成折线图,我们会发现明显的二段性,我们以D点作为参照物,会发现折线AB上的值全部大于D点的值,折线CD上的值都小于或等于D点的值。所以我们找到C点对应的值即为最小值即可

image.png

  1. 当mid值落在AB区间时,此时该区间一定不存在最小值,所以在更新left到mid位置时,让left=mid+1
  2. 当mid值落在CD区间时,此时该区间存在最小值,所以更新right时不能越过mid的位置,让right=mid

image.png

代码实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0,right = nums.size()-1;
        int x =nums[right];  //表示最后一个位置的值
        while(left < right)
        {
            int mid = left+(right-left)/2;
            if(nums[mid] > x) left = mid+1;
            else right=mid;
        }
        return nums[left];
    }
};

0~n-1缺失的数字

0~n-1缺失的数字

题目解析

⼀个⻓度为n-1的递增排序数组中的所有数字都是唯⼀的,并且每个数字都在范围0〜n-1之内。在范围0〜n-1内的n个数字中有且只有⼀个数字不在该数组中,请找出这个数字

算法原理

  1. 解法一:借助容器哈希表:n个数,建立一个n+1大小的哈希表,然后向哈希表里填入,填完后观察哪个位置没有填到,即为确实的数字
  2. 解法二:直接遍历
  3. 解法三:位运算:用异或操作,将缺失的数组与正常的数组进行异或(异或操作:相同的数会抵消),缺少的数因为没有对应的数字和它进行异或操作抵消,所以最后异或的结果就是缺少的数。

image.png

  1. 解法四:数学方法——高斯求和公式。先对正常数组进行求和(高中的等差数列),然后依次减去缺失数组的数,剩下的数字即为缺失的数字

以上解法时间复杂度都是O(n),哈希表解法中还有个O(n)的空间复杂度

  1. 解法五:二分查找:左边区间数组下标的值与正常的数组下标一一对应,右边区间数组中数字下标与正常的不是一一对应;即发现该数组的二段性。我们需要找的结果就在五角星位置,即右边区间最左边的位置image.png

    1. 当mid落在左边区间时,判读条件为下标值是否一一对应,更新left,left=mid+1;
    2. 当mid落在右边区间时,更新right,因为mid有可能在最终结果上,所以不能跳过,让right=mid;image.png
    3. 这里还有个细节问题,如下图这个数组是完全递增的数组,该数组缺少的数字是4,但是我们的二分查找找的是右边区间的左端点。我们发现这个数组根本不存在右区间,此时二分的结果落在了3这个位置,但这个位置的值并不是我们需要的结果,而是该位置的后一个位置。所以最终返回的时候需要判断,当最后left和right相等时,此时所指的位置的值的下标与其相等,说明该数组是一个完全递增的数组,我们缺失的数字时left和right下一个位置。(返回left+1)

image.png

代码实现

class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
        int left = 0, right = records.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }

        //返回left和right都行
        //处理细节问题  
        return left == records[left] ? left + 1 : left;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/219490.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AI交互数字人如何成为古镇文化传播者?

近日&#xff0c;南浔古镇出现了5位数字人&#xff0c;将古镇文化与数字人相结合&#xff0c;实现旅游营销的创新尝试。数字人不仅可以作为南浔古镇的品牌形象&#xff0c;还可以作为南浔古镇的文化传播者&#xff0c;化身AI交互数字人与游客互动交流&#xff0c;讲述南浔古镇的…

面了一个测试工程师要求月薪26K,总感觉他背了很多面试题

最近有朋友去华为面试&#xff0c;面试前后进行了20天左右&#xff0c;包含4轮电话面试、1轮笔试、1轮主管视频面试、1轮hr视频面试。 据他所说&#xff0c;80%的人都会栽在第一轮面试&#xff0c;要不是他面试前做足准备&#xff0c;估计都坚持不完后面几轮面试。 其实&…

操作系统复习总结——文件管理

&#x1f525;博客主页&#xff1a;真的睡不醒 &#x1f680;系列专栏&#xff1a;深度学习环境搭建、环境配置问题解决、自然语言处理、语音信号处理、项目开发 &#x1f498;每日语录&#xff1a;但愿每次回忆&#xff0c;对生活都不感到负疚。 &#x1f389;感谢大家点赞…

如何模拟多台物理设备有效防止账号关联?

一般来说&#xff0c;对于有大量业务和多账号需求的用户来说&#xff0c;他们需要准备多台物理设备和多条网络线路&#xff0c;才有可能防止多个业务或者多个账号之间产生关联。目前&#xff0c;出现了一种新型解决方案——指纹浏览器。本文将介绍这种浏览器是如何模拟设备&…

Python接口自动化测试:断言封装详解!

前言 在进行API接口测试时&#xff0c;断言起着至关重要的作用。断言是用于验证预期结果与实际结果是否一致的过程。在Python中&#xff0c;我们可以利用一些库来实现断言功能。 1. 安装必要的库 在Python中&#xff0c;我们主要会使用两个库&#xff1a;requests和jsonpath…

微信小程序基础

1.小程序发展史 微信小程序之前&#xff0c;是使用weixin-sdk进行开发&#xff0c;调用视频&#xff0c;摄像头等。 微信小程序weixin up端&#xff0c;所以PC端的window这些没有&#xff0c;运行环境是IOS&#xff0c;安卓等&#xff0c;有一些特殊的调用录音功能&#xff0…

Canal笔记:安装与整合Springboot模式Mysql同步Redis

官方文档 https://github.com/alibaba/canal 使用场景 学习一件东西前&#xff0c;要知道为什么使用它。 1、同步mysql数据到redis 常规情况下&#xff0c;产生数据的方法可能有很多地方&#xff0c;那么就需要在多个地方中&#xff0c;都去做mysql数据同步到redis的处理&…

YOLOv3 快速上手:Windows 10上的训练环境搭建

文章目录 前言一、前期准备二、基础环境准备1. 创建虚拟环境2. 打开Terminal3. 下载YOLOv3运行环境 三、PyCharm关联3.1 运行PyCharm3.2 关联Anaconda虚拟环境 四、运行环境检查1. 检查requirements.txt文件2. 安装依赖 五、运行代码5.1 运行检测代码5.2 运行训练代码 六、常见…

零信任组件和实施

零信任是一种安全标准&#xff0c;其功能遵循“从不信任&#xff0c;始终验证”的原则&#xff0c;并确保没有用户或设备受信任&#xff0c;无论他们是在组织网络内部还是外部。简而言之&#xff0c;零信任模型消除了信任组织安全边界内任何内容的概念&#xff0c;而是倡导严格…

如何计算 ChatGPT 的 Tokens 数量?

一、基本介绍 随着人工智能大模型技术的迅速发展&#xff0c;一种创新的计费模式正在逐渐普及&#xff0c;即以“令牌”&#xff08;Token&#xff09;作为衡量使用成本的单位。那么&#xff0c;究竟什么是Token呢&#xff1f; Token 是一种将自然语言文本转化为计算机可以理…

vue2项目中添加字体文件

vue2项目中添加字体文件 1、下载相关文件&#xff0c;放置文件夹中&#xff0c;这里我是在assets文件中新建了fontFamily 2、在assets文件中新建css文件 3、在页面中使用 <style lang"less" scoped> import ../../assets/css/fonts.less;.total-wrap {displa…

esp32使用命令查看芯片flash大小以及PSRAM的大小

在idf.py命令窗口中输入 esptool.py -p COM* flash_id 其中COM*是连接你的esp32芯片的端口号。

蓝桥杯算法心得——想吃冰淇淋和蛋糕(dp)

大家好&#xff0c;我是晴天学长&#xff0c;dp题&#xff0c;怎么设计状态很重要&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .想吃冰淇淋和蛋糕 想吃冰淇淋与蛋糕 输入格式 第一行输入一个整数n。…

认识异常 ---java

目录 一. 异常的概念 二. 异常的体系结构 三. 异常的分类 三. 异常的处理 3.1 异常的抛出throw 3.2. 异常声明throws 3.3 捕获并处理try-catch finally 3.4异常的处理流程 四. 自定义异常类 一. 异常的概念 在 Java 中&#xff0c;将程序执行过程中发生的不正常行为称为…

设计模式之结构型模式(适配器、桥接、组合、享元、装饰者、外观、代理)

文章目录 一、结构型设计模式二、适配器模式三、桥接模式四、组合模式五、享元模式六、装饰者模式七、外观模式八、代理设计模式 一、结构型设计模式 这篇文章我们来讲解下结构型设计模式&#xff0c;结构型设计模式&#xff0c;主要处理类或对象的组合关系&#xff0c;为如何…

怎样实现燃气产业的数字化转型之路?

关键词&#xff1a;智慧燃气、燃气数字化、智慧燃气建设、智慧燃气解决方案、智慧燃气平台 燃气产业不仅是我国能源的支柱产业&#xff0c;更是推进经济建设与生态保护协同发展的主战场。数字技术与企业生产、经营及管理深度融合是驱动企业转型升级的重要路径。基于产业融合视…

【bash指令全集合】最全教程-持续更新!

作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&#xff0c;目前于新西兰奥克兰大学攻读IT硕士学位。荣誉&#xff1a;阿里云博客专家认证、腾讯开发者社区优质创作者&#xff0c;在CTF省赛校赛多次取得好成绩。跨领域…

智慧工地源码 SaaS模式云平台

伴随着技术的不断发展&#xff0c;信息化手段、移动技术、智能穿戴及工具在工程施工阶段的应用不断提升&#xff0c;智慧工地概念应运而生&#xff0c;庞大的建设规模催生着智慧工地的探索和研发。 什么是智慧工地&#xff1f; 伴随着技术的不断发展&#xff0c;信息化手段、移…

基于Jenkins实现接口自动化持续集成

一、JOB项目配置 1、添加描述 可选选项可填可不填 2、限制项目的运行节点 节点中要有运行环境所需的配置 节点配置教程&#xff1a;https://blog.csdn.net/YZL40514131/article/details/131504280 3、源码管理 需要将脚本推送到远程仓库中 4、构建触发器 可以选择定时构建…

内衣迷你洗衣机什么牌子好?好用不贵的内衣洗衣机推荐

由于内衣洗衣机在目前的市场上越来越受欢迎&#xff0c;使得不少的小伙伴都在犹豫要不要为自己入手一台专用的内衣洗衣机&#xff0c;专门来清洗一些内衣裤等等贴身衣物&#xff0c;这个问题的答案是很有必要的&#xff0c;因为目前市场上的家用大型洗衣机对衣物只能够起到清洁…