【刷题】二分查找进阶

叫我龙翔

发布于 2024-04-21 08:34:57

950

发布于 2024-04-21 08:34:57

1 前言

二分查找的算法思想是很好理解的。朴素二分很容易，但一般常使用左端点查找与右端点查找来解决问题。模版：

        int left = 0 , right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            //int mid = left + (right - left + 1) / 2;
            if(  // 判断条件 )
            {
                left = mid + 1;
                //left = mid 
            }
            else
            {
                right = mid;
                // right = mid - 1
            }
        }
        return left;
        //return right ;

while（）循环条件是left < right !
注意对应关系。right里有 -1 那么对应的求中值就要有+1。把握这个规律，就不会弄乱了

下面来看几道例题，强化训练二分查找的算法思路！通过这些题的训练，就可以很熟悉二分查找算法的思想，以后遇到问题就多了一种解决手段！！！

Leetcode 852. 山脉数组的峰顶索引

上链接：852. 山脉数组的峰顶索引！！！

题目描述

首先我们要理解什么是山峰数组，根据题目的描述，山峰数组就是先升再下降的数组。我们要在其中寻找峰值的索引。这个问题看起来看还是挺简单的

算法思路

首先我们要判断该数组是否存在二段性？？？当然有了！

以峰值为分割，左边都是nums[n] < nums[n + 1] 右边都是nums[n] > nums[n + 1]

通过这个二段性我们可以来进行二分查找：

如果中值落在左边，那么left 应该移动到 mid + 1(因为nums[n] < nums[n + 1] ，mid对应的值一定不是峰值)
如果中值落在右边，那么right 应该移动到 mid(因为nums[n] > nums[n + 1] ，mid对应的值有可能是峰值)

有了思路，代码很简单就可以写出来，直接套用模版。

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

提交：过啦！！！！

Leetcode 162. 寻找峰值

家人们！！！跟上节奏：162. 寻找峰值

题目描述

这道题是上面求峰值索引的变形。这道题具有多个封值（换句话说数组是无序的），那么我们要在无序的数组寻找一个峰值。

算法思路

首先我们来看可不可以判断出来数组的二段性。和求峰值索引一样：

以其中一个峰值为分割，左边一部分是nums[n] < nums[n + 1] 右边一部分是nums[n] > nums[n + 1]

那么根据这个二段性也就是可以写出算法逻辑了：

如果中值落在左边，那么left 应该移动到 mid + 1(因为nums[n] < nums[n + 1] ，右边一定存在一个峰值，mid对应的值一定不是峰值)
如果中值落在右边，那么right 应该移动到 mid(因为nums[n] > nums[n + 1] ，左边一定存在一个峰值，mid对应的值有可能是峰值)

有了思路，直接套用模版秒了！！！

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])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }
};

提交过啦！！！

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

上链接！！！153. 寻找旋转排序数组中的最小值

题目描述

根据题目描述啊，是很好理解的，就是将一个有序的数组进行移动，使其旋转，形成一个先增长然后断崖后再增长的数组，我们要找到其中的最小值

算法思路

这个题的暴力算法很简单（我们不考虑），首先也是来分析二段性。这个二段性如何进行分析呢？？？

以其中数组末位值为分割，由于旋转的特性，左边一部分是大于末位值 右边一部分是小于等于末位值

然后根据二段性进行算法分析：

如果中值落在左边，那么left 应该移动到 mid + 1(左边一定不存在最小值，mid 对应的值一定不是最小值)
如果中值落在右边，那么right 应该移动到 mid(右边一定不存在一个峰值，mid对应的值有可能是最小值)

根据算法逻辑，直接秒杀：

class Solution {
public:
    int findMin(vector<int>& nums) {
        //分析二段性质
        //左边都大于 末位数字 右边都 小于等于 末尾数字
        int left = 0;
        int right = nums.size() - 1;

        while(left < right)
        {
            int mid = left +(right - left) / 2;
            //说明mid 在最小值 左边 
            if(nums[mid] > nums[nums.size() - 1])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        return nums[left];
    }
};

提交：过啦！！！

Leetcode LCR 173. 点名

最后一道：LCR 173. 点名！！！

题目描述

题目非常简单奥，就是寻找断点。（有坑哦）

算法思路

暴力算法有很多种：遍历，位运算，数学公式。我们来用更快速的二分查找算法首先来分析二段性，这个其实不太好想

以其中断点为分割，左边一部分是数组值与下标相等 ，右边一部分是数组值与下标不相等

根据这个二段性我们就可以来进行算法分析：

如果中值落在左边，那么left 应该移动到 mid + 1(左边一定不存在断点，mid 对应的值一定不是断点)
如果中值落在右边，那么right 应该移动到 mid(mid对应的值有可能是断点)
注意如果最后left到了最右边，那么缺少的是最后一名同学，要进行一个判断

根据这个算法逻辑，我们书写代码：

class Solution {
public:
    int takeAttendance(vector<int>& nums) {
        //寻找二段性
        //左边下标对应 右边下标不对应
        int left = 0 ; 
        int right = nums.size() - 1;

        while(left < right)
        {
            int mid = left + (right - left ) / 2;
            //
            if(nums[mid] == mid)
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        //left到了最右边,缺少的是最后一名同学，要进行一个判断
        return nums[left] == left ? nums.size() : left ;
    }
};

提交过啦！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-20，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度