算法专题(三)：二分查找

本篇还是像之前一样，以举例子的形式向大家讲解！每道题的题目均是传送门！点击跳转对应题！

目录

一、二分查找 

1.1 题目

1.2 思路

1.3 代码实现

总结（模版）

朴素版：

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

2.1 题目

2.2 思路

2.3 代码实现

总结（模版）

三、搜索插入位置 

3.1 题目

3.2 思路

3.3 代码实现

四、x 的平方根

4.1 题目

4.2 思路

4.2 代码实现

暴力：

二分查找：

​编辑

五、山脉数组的峰顶索引 

5.1 题目

5.2 思路

5.3 代码实现

暴力：

二分查找：

六、寻找峰值

6.1 题目

6.2 思路

6.3 代码实现

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

7.1 题目

7.2 思路

7.3 代码实现

八、点名（0～n-1 中缺失的数字）

8.1 题目

8.2 思路

8.3 代码实现

一、二分查找 

1.1 题目

1.2 思路

暴力解法就是，从左向右依次遍历，直到找到target，返回其下标

1. 定义 left ， right 指针，分别指向数组的左右区间。
2. 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
        i. arr[mid] == target 说明正好找到，返回 mid 的值；        
        ii. arr[mid] > target 说明 [mid, right] 这段区间都是大于 target 的，因此舍去右边区间，在左边 [left, mid -1] 的区间继续查找，即让 right = mid -1 ，然后重复 2 过程；
        iii. arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的，因此舍去左边区间，在右边 [mid + 1, right] 区间继续查找，即让 left = mid +1 ，然后重复 2 过程；
3. 当 left 与 right 错开时，说明整个区间都没有这个数，返回 -1 。 

1.3 代码实现

直接 mid = (left + right)/2;  left+right 是有可能溢出的，所以我们改用让left向右移动一半的距离

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;
    }
};

总结（模版）

朴素版：

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

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

2.1 题目

2.2 思路

为了方便叙述，下面我用 x 表示该元素， resLeft 表示左边界， resRight 表示右边界。

•寻找左边界：
        我们注意到以左边界划分的两个区间的特点：
                ▪ 左边区间 [left, resLeft - 1] 都是小于 x 的；
                ▪ 右边区间（包括左边界） [resLeft, right] 都是大于等于 x 的；
                • 因此，关于 mid 的落点，我们可以分为下面两种情况：
        当我们的 mid 落在 [left, resLeft - 1] 区间的时候，也就是 arr[mid] <target 。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid + 1, right] 上寻找左边界；
        当 mid 落在 [resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；

 注意：这里找中间元素需要向下取整。
因为后续移动左右指针的时候：
        • 左指针： left = mid + 1 ，是会向后移动的，因此区间是会缩小的；
        • 右指针： right = mid ，可能会原地踏步（比如：如果向上取整的话，如果剩下 1,2 两个元素， left == 1 ， right == 2 ， mid == 2 。更新区间之后， left，right，mid 的值没有改变，就会陷入死循环）。
因此一定要注意，当 right = mid 的时候，要向下取整。

寻右左边界：
        ◦ 用 resRight 表示右边界；
        ◦ 我们注意到右边界的特点：
                ▪ 左边区间 （包括右边界） [left, resRight] 都是小于等于 x 的；
                ▪ 右边区间 [resRight+ 1, right] 都是大于 x 的；
                • 因此，关于 mid 的落点，我们可以分为下面两种情况：
        ◦ 当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果） 都是可以舍去的，此时更新 left 到 mid的位置； ◦ 当 mid 落在 [resRight+ 1, right] 的区间的时候，说明 [mid, right] 内的元素是可以舍去的，此时更新 right 到 mid - 1 的位置；
                • 由此，就可以通过二分，来快速寻找右边界；

注意：这里找中间元素需要向上取整。
因为后续移动左右指针的时候：
        • 左指针： left = mid ，可能会原地踏步（比如：如果向下取整的话，如果剩下 1,2 两个元素， left == 1， right == 2，mid == 1 。更新区间之后， left，right，mid 的值没有改变，就会陷入死环）。
        • 右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩小的；
        因此一定要注意，当 right = mid 的时候，要向下取整。

2.3 代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.size() == 0)
            return {-1,-1};
        int begin = 0;
        //二分左端点
        int left = 0,right = nums.size()-1;
        while(left < right)
        {
            int mid = left+(right-left)/2;
            if(target > nums[mid])
                    left = mid+1;
            else
                right = mid;
        }
        if(target != nums[left]) //判断是否有结果
            return {-1,-1};
        else
            begin = left;  //标记下一处端点
        right = nums.size()-1;
        //二分右端点
        while(left<right)
        {
            int mid = left +(right-left+1)/2;
            if(target >= nums[mid])
                left = mid;
            else
                right = mid-1;
        }
        return {begin,right};
    }
};

总结（模版）

请大家一定不要觉得背下模板就能解决所有二分问题（不要死记模版）。二分问题最重要的就是要分析题意，然后确定要搜索的区间，根据分析问题来写出二分查找算法的代码。

1. 关于什么时候用三段式，还是二段式中的某一个，一定不要强行去用，而是通过具体的问题分析情况，根据查找区间的变化确定指针的转移过程，从而选择一个模板。
2. 当选择两段式的模板时：
        在求 mid 的时候，只有 right - 1 的情况下，才会向上取整（也就是 +1 取中间数）

三、搜索插入位置 

3.1 题目

3.2 思路

1. 分析插入位置左右两侧区间上元素的特点：
        设插入位置的坐标为 index ，根据插入位置的特点可以知道：
        • [left, index - 1] 内的所有元素均是小于 target 的；
        • [index, right] 内的所有元素均是大于等于 target 的。
2. 设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信息，分析下一轮查询的区间：
        ▪ 当 nums[mid] >= target 时，说明 mid 落在了 [index, right] 区间上，mid 左边包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [left,mid] 上。因此，更新 right 到 mid 位置，继续查找。
        ▪ 当 nums[mid] < target 时，说明 mid 落在了 [left, index - 1] 区间上，mid 右边但不包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [mid+ 1, right] 上。因此，更新 left 到 mid + 1 的位置，继续查找。
3. 直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果。

3.3 代码实现

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;
        }
        if(nums[left] < target)
            return left+1;
        return left;
    }
};

四、x 的平方根

4.1 题目

4.2 思路

暴力解法：

依次枚举 [0, x] 之间的所有数 i ：（这里没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了，往后的情况就不会再判断。反而研究枚举区间，既耽误时间，又可能出错）
▪ 如果 i * i == x ，直接返回 x ；
▪ 如果 i * i > x ，说明之前的一个数是结果，返回 i - 1 。
由于 i * i 可能超过 int 的最大值，因此使用 long long 类型。

二分查找：

4.2 代码实现

暴力：

class Solution {
public:
int mySqrt(int x) 
{
    // 由于两个较大的数相乘可能会超过 int 最大范围
    // 因此用 long long
    long long i = 0;
    for (i = 0; i <= x; i++)
    {
        // 如果两个数相乘正好等于 x，直接返回 i
        if (i * i == x) return i;
        // 如果第一次出现两个数相乘大于 x，说明结果是前一个数
        if (i * i > x) return i - 1;
    }
        // 为了处理oj题需要控制所有路径都有返回值
    return -1;
    }
};

二分查找：

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

五、山脉数组的峰顶索引 

5.1 题目

5.2 思路

暴力枚举（时间：O(N)）：

峰顶的特点：比两侧的元素都要大。
因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。

二分查找：

1. 分析峰顶位置的数据特点，以及山峰两旁的数据的特点：
        ◦ 峰顶数据特点： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；
        ◦ 峰顶左边的数据特点： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是呈现上升趋势；
        ◦ 峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是呈现下降趋势。
2. 因此，根据 mid 位置的信息，我们可以分为下面三种情况：
        ◦ 如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；
        ◦ 如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索；
        ◦ 如果 mid 位置就是山峰，直接返回结果。

5.3 代码实现

暴力：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
{
        int n = arr.size();
        // 遍历数组内每一个元素，直到找到峰顶
        for (int i = 1; i < n - 1; i++)
            // 峰顶满足的条件
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
                return i;

        // 为了处理 oj 需要控制所有路径都有返回值
        return -1;
}
};

二分查找：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {   //第一个位置和最后一个位置不可能是结果
        int left = 1,right = arr.size()-2; 
        while(left < right)
        {
            int mid = left + (right-left+1)/2;
            if(arr[mid] > arr[mid-1]) left = mid;
            else right = mid -1;
        }
        return left;
    }
};

六、寻找峰值

6.1 题目

6.2 思路

寻找二段性：
        任取一个点 i ，与下一个点 i + 1 ，会有如下两种情况：
                • arr[i] > arr[i + 1] ：此时「左侧区域」一定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；
                • arr[i] < arr[i + 1] ：此时「右侧区域」一定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。
        当我们找到「二段性」的时候，就可以尝试用「二分查找」算法来解决问题。

6.3 代码实现

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;
    }
};

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

7.1 题目

7.2 思路

关于暴力查找，只需遍历一遍数组，这里不再赘述 ，时间复杂度：O(N)

其中 C 点就是我们要求的点。
二分的本质：找到一个判断标准，使得查找区间能够一分为二。
通过图像我们可以发现， [A，B] 区间内的点都是严格大于 D 点的值的， C 点的值是严格小于 D 点的值的。但是当 [C，D] 区间只有一个元素的时候， C 点的值是可能等于 D 点的值的。
因此，初始化左右两个指针 left ， right ：
        然后根据 mid 的落点，我们可以这样划分下一次查询的区间：
                ▪ 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格大于 D 点的值，下一次查询区间在 [mid + 1，right] 上；
                ▪ 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格小于等于 D 点的值，下次查询区间在 [left，mid] 上。
        当区间长度变成 1 的时候，就是我们要找的结果。

7.3 代码实现

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

八、点名（0～n-1 中缺失的数字）

8.1 题目

8.2 思路

关于这道题中，时间复杂度为 O(N) 的解法有很多种，比如哈希表，直接遍历查找，位运算，高斯求和公式。
这里就只讲解一个二分法，来解决这个问题。
在这个升序的数组中，我们发现：
        ▪ 在第一个缺失位置的左边，数组内的元素都是与数组的下标相等的；
        ▪ 在第一个缺失位置的右边，数组内的元素与数组下标是不相等的。
因此，我们可以利用这个「二段性」，来使用「二分查找」算法。

8.3 代码实现

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;
        }
        if(records[left] == left)
            return left+1;
        else    
            return left;
    }
};

本篇完，下篇见！大家一定要分析过程，不要死记模版！

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

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

相关文章

C# OpenCvSharp 部署文档矫正，包括文档扭曲/模糊/阴影等情况

C# OpenCvSharp 部署文档矫正，包括文档扭曲/模糊/阴影等情况

目录 说明 效果 模型 项目 代码 下载 参考 C# OpenCvSharp 部署文档矫正&#xff0c;包括文档扭曲/模糊/阴影等情况 说明 地址&#xff1a;https://github.com/RapidAI/RapidUnDistort 修正文档扭曲/模糊/阴影等情况&#xff0c;使用onnx模型简单轻量部署&#xff0c…
阅读更多...
Excel 技巧15 - 在Excel中抠图头像，换背景色(★★）

Excel 技巧15 - 在Excel中抠图头像，换背景色(★★）

本文讲了如何在Excel中抠图头像&#xff0c;换背景色。 1&#xff0c;如何在Excel中抠图头像&#xff0c;换背景色 大家都知道在PS中可以很容易抠图头像&#xff0c;换背景色&#xff0c;其实Excel中也可以抠简单的图&#xff0c;换背景色。 ※所用头像图片为百度搜索&#x…
阅读更多...
吴恩达深度学习——神经网络介绍

吴恩达深度学习——神经网络介绍

文章内容来自BV11H4y1F7uH&#xff0c;仅为个人学习所用。 文章目录 什么是神经网络引入神经网络神经元激活函数ReLU隐藏单元 用神经网络进行监督学习监督学习与无监督学习举例 什么是神经网络 引入 已经有六个房子的数据集&#xff0c;横轴为房子大小&#xff0c;纵轴为房子…
阅读更多...
xctf-comment（Intruder，git恢复，SQL注入，Hex解码）

xctf-comment（Intruder，git恢复，SQL注入，Hex解码）

这题是2018年网鼎杯真题&#xff0c;考察 Burp Suite 的 Intruder 模块去找用户密码&#xff0c;使用 githacker 恢复代码&#xff08;githack不行&#xff09;&#xff0c;代码审计发现SQL二次注入&#xff0c;尝试SQL注入读取文件内容&#xff0c;读取的是/home/www/.bash_hi…
阅读更多...
分布式系统通信解决方案：Netty 与 Protobuf 高效应用

分布式系统通信解决方案：Netty 与 Protobuf 高效应用

分布式系统通信解决方案&#xff1a;Netty 与 Protobuf 高效应用 一、引言 在现代网络编程中&#xff0c;数据的编解码是系统设计的一个核心问题&#xff0c;特别是在高并发和低延迟的应用场景中&#xff0c;如何高效地序列化和传输数据对于系统的性能至关重要。随着分布式系…
阅读更多...
C++《AVL树》

C++《AVL树》

在之前的学习当中我们已经了解了二叉搜索树&#xff0c;并且我们知道二叉搜索树的查找效率是无法满足我们的要求&#xff0c;当二叉树为左或者右斜树查找的效率就很低下了&#xff0c;那么这本篇当中我们就要来学习对二叉搜索树进行优化的二叉树——AVL树。在此会先来了解AVL树…
阅读更多...
ToDesk设置临时密码和安全密码都可以当做连接密码使用

ToDesk设置临时密码和安全密码都可以当做连接密码使用

ToDesk 在各领域办公都已经是非常常见了 为了安全 ToDesk 设置了连接密码&#xff0c;想连接 需要输入远程码和连接密码 我们刚打开 系统默认给我们用的是临时密码&#xff0c;安全性确实很强 和定时Tokey一样&#xff0c;固定时间切换。 但是 如果我们要经常连接这个电脑&a…
阅读更多...
LLMs（大型语言模型）的多智能体：Auto-GPT

LLMs（大型语言模型）的多智能体：Auto-GPT

LLMs（大型语言模型）的多智能体：Auto-GPT 是指在一个系统中集成多个具有不同能力、角色和任务的智能体，这些智能体能够相互协作、沟通和交互，以共同完成复杂的任务或解决复杂的问题。每个智能体都可以被视为一个独立的实体，具有自己的策略、目标和知识库，通过相互之间的…
阅读更多...
【Linux环境变量与命令行参数】常见环境变量 | 环境变量的全局属性 | 命令行参数

【Linux环境变量与命令行参数】常见环境变量 | 环境变量的全局属性 | 命令行参数

前言 本文中主要介绍PATH、HOME、SHELL、HISTSIZE这4个环境变量&#xff0c;其中详细介绍PATH。并理解环境变量的全局属性--环境变量可以被子进程继承&#xff0c;这里要注意和C中的继承进行区分。其次&#xff0c;介绍命令行参数--mian函数的参数。 1.环境变量的基本概念 在…
阅读更多...
【Python】函数（二）

【Python】函数（二）

链式调用 # 判定是否是奇数 def isOdd(num):if num % 2 0:return Falseelse:return Trueresult isOdd(10) print(result)实际上也可以简化写作 print(isOdd(10))把一个函数的返回值, 作为另一个函数的参数, 这种操作称为 链式调用 嵌套调用 函数内部还可以调用其他的函数…
阅读更多...
【Elasticsearch 】 聚合分析：桶聚合

【Elasticsearch 】 聚合分析：桶聚合

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…
阅读更多...
学习ASP.NET Core的身份认证（基于JwtBearer的身份认证7）

学习ASP.NET Core的身份认证（基于JwtBearer的身份认证7）

本文验证基于请求头中传递token信息的认证方式&#xff0c;webapi项目的控制器类中新建如下函数&#xff0c;仅通过验证的客户端能调用&#xff0c;需要客户端请求在Header中添加’Authorization’: Bearer token’的键值对且通过token验证后才能调用。 [Authorize] [HttpGet]…
阅读更多...
游戏AI，让AI 玩游戏有什么作用？

游戏AI，让AI 玩游戏有什么作用？

让 AI 玩游戏这件事远比我们想象的要早得多。追溯到 1948 年&#xff0c;图灵和同事钱伯恩共同设计了国际象棋程序 Turochamp。之所以设计这么个程序&#xff0c;图灵是想说明&#xff0c;机器理论上能模拟人脑能做的任何事情&#xff0c;包括下棋这样复杂的智力活动。 可惜的是…
阅读更多...
9. 神经网络（一.神经元模型）

9. 神经网络（一.神经元模型）

首先&#xff0c;先看一个简化的生物神经元结构&#xff1a; 生物神经元有多种类型&#xff0c;内部也有复杂的结构&#xff0c;但是可以把单个神经元简化为3部分组成&#xff1a; 树突&#xff1a;一个神经元往往有多个树突&#xff0c;用于接收传入的信息。轴突&#xff1a;…
阅读更多...
Docker可视化管理工具Portainer

Docker可视化管理工具Portainer

Portainer简介 Portainer 是一个轻量级的、开源的容器管理工具&#xff0c;提供了一个直观的 Web 用户界面&#xff08;UI&#xff09;&#xff0c;用于管理 Docker 和 Kubernetes 环境。它简化了容器的部署、监控和管理&#xff0c;特别适合不熟悉命令行操作的用户或团队。 …
阅读更多...
maven helper插件使用

maven helper插件使用

在intellij idea插件市场搜索maven help并安装安装好后会多一个Dependency Analyzer 场景1&#xff1a;排除某个依赖 点击完exclude pom文件会被修改 然后刷新下maven&#xff0c;相应的依赖就会被排除了。
阅读更多...
【VRChat · 改模】Unity2019、2022的版本选择哪个如何决策，功能有何区别；

【VRChat · 改模】Unity2019、2022的版本选择哪个如何决策，功能有何区别；

总览 1.Unity2019、2022的版本的选择 2.Unity添加着色器教程 一、Unity2019、2022的版本的选择 1.Unity2019 和 Unity2022 的区别&#xff0c;VRChat SDK 为何要区分两个版本 我是外行&#xff0c;最开始以为的是&#xff0c;2019 和 2022 的变化是基于这个模型本身的。 也…
阅读更多...
RHCE实验详解

RHCE实验详解

目录 实验分析 环境拓扑结构 项目需求 主机环境描述 实验步骤 一、密钥互信和主机名更改 二、DNS 三、NGINX 四、MARIADB 五、NFS 六、NTP 七、论坛服务 结果展示及痛点解答 实验分析 环境拓扑结构 项目需求 1. 172.25.250.101 主机上的 Web 服务要求提供 www.ex…
阅读更多...
学Python的人…

学Python的人…

学Python的人… 一、Python能干什么&#xff1f; 1.爬虫&#xff1a;前几年&#xff0c;深度学习还没发展起来的时候&#xff0c;书店里Python就和爬虫挂钩&#xff0c;因为Python写爬虫确实方便。 2.数据分析&#xff1a;Python有各种的数据分析库可以方便使用&#xff0…
阅读更多...
docker 安装 mysql 详解

docker 安装 mysql 详解

在平常的开发工作中&#xff0c;我们经常需要用到 mysql 数据库。那么在docker容器中&#xff0c;应该怎么安装mysql数据库呢。简单来说&#xff0c;第一步&#xff1a;拉取镜像&#xff1b;第二步&#xff1a;创建挂载目录并设置 my.conf&#xff1b;第三步&#xff1a;启动容…
阅读更多...
最新文章

Copyright @ 2022~2023