算法练习：二分查找

目录

  • 1. 朴素二分查找
  • 2. 在排序数组中查找元素的第一个和最后一个位置
  • 3. 搜索插入位置
  • 4. x的平方根
  • 5. 山脉数组的峰值索引
  • 6. 寻找峰值
  • 7. 寻找旋转排序数组中的最小值
  • 8. 点名

1. 朴素二分查找

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二分查找
  3. 二分查找的使用前提为数据具有"二段性"，在二分时，并不一定要进行2等分（1/3，1/4…）
  4. 二分查找的时间复杂度：O( l o g N log^N logN)

在这里插入图片描述

  1. 求mid的算法优化（原算法有溢出风险）

在这里插入图片描述

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int right = nums.size() - 1;
        int left = 0;
        while(right >= left)
        {
            //此种算法存在溢出风险
            //int mid = (right + left) / 2;
            int mid = (right - left) / 2 + left;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }

            if(nums[mid] < target)
            {
                left = mid + 1;
            }

            if(nums[mid] == target)
            {
                return mid;
            }
        }

        return -1;
    }
};

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

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    在排序数组查找元素的第一个与最后一个位置
  3. 思路：向符合条件位置不断推进

在这里插入图片描述

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        int right = nums.size() - 1;
        int left = 0;
        vector<int> count(2,-1);

        //数据为空，特殊处理
        if(nums.size() == 0)
        {
            return count;
        }
        //左端点
        while(left < right)
        {
            //落到左区间
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target)
            {
                right = mid;
            }

            if(nums[mid] < target)
            {
                left = mid + 1;
            }
        }

        if(nums[left] == target)
        {
            count[0] = left;
        }

        right = nums.size() - 1;
        left = 0;
        //右端点
        while(left < right)
        {
            //落到右区间
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }

            if(nums[mid] <= target)
            {
                left = mid;
            }
        }

        if(nums[left] == target)
        {
            count[1] = left;
        }

        return count;
    }
};

3. 搜索插入位置

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    搜索插入位置
  3. 思路：取大，右区间的左边界
class Solution 
{
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0;
        int right = nums.size();
        while(left < right)
        {
            //小于，大于等于
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }

            if(nums[mid] >= target)
            {
                right = mid;
            }
        }

        return left;
    }
};

4. x的平方根

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    x的平方根
  3. 思路：暴力解法的优化，左区间的右边界，二段性
class Solution 
{
public:
    int mySqrt(int x) 
    {
        if(x < 1)
        {
            return 0;
        }
        int left = 1;
        int right = x;
        while(left < right)
        {
            //当left从0开始时，left + 1可能会溢出
            long long mid = left + (right - left + 1) / 2;//防止溢出
            if(mid * mid <= x)
            {
                left = mid;
            }

            if(mid * mid > x)
            {
                right = mid - 1;
            }
        }

        return left;
    }
};

5. 山脉数组的峰值索引

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    山脉数组的峰值索引
  3. 思路：二分法，左区间右边界

在这里插入图片描述

class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& nums) 
    {
        //左区间，右边界
        int left = 0;
        int right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > nums[mid - 1])
            {
                left = mid;
            }

            if(nums[mid] < nums[mid - 1])
            {
                right = mid - 1;
            }
        }

        return left;
    }
};
  1. 右区间的左边界

在这里插入图片描述

class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& nums) 
    {
        //右区间，左边界
        int left = 0;
        int right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1])
            {
                left = mid + 1;
            }

            if(nums[mid] > nums[mid + 1])
            {
                right = mid;
            }
        }

        return left;
    }
};

6. 寻找峰值

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    寻找峰值
  3. 思路：二段性，右区间的左边界，不足三个数特殊化处理

在这里插入图片描述

class Solution 
{
public:
    int findPeakElement(vector<int>& nums) 
    {
        int left = 0;
        int right = nums.size() - 1;
        //特殊情况
        //数组值小于3
        if (nums.size() < 2)
        {
            return 0;
        }

        if (nums.size() < 3)
        {
            return nums[0] > nums[1] ? 0 : 1;
        }

        //右区间的左边界
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1])
            {
                left = mid + 1;
            }

            if (nums[mid] > nums[mid + 1])
            {
                right = mid;
            }
        }

        return left;
    }
};

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

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    寻找寻转排序数组中的最小值
  3. 思路：右区间，左边界
class Solution 
{
public:
    int findMin(vector<int>& nums) 
    {
        //二段性，右区间，左边界
        int right = nums.size() - 1;
        int left = 0;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[right])
            {
                left = mid + 1;
            }

            if(nums[mid] < nums[right])
            {
                right = mid;
            }
        }

        return nums[left];
    }
};

8. 点名

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    点名
  3. 思路：（多解法，考察知识广度）
    <1>二分法：右区间的左边界，学号等于下标，学号大于下标，边界问题！
    <2> 哈希表法：时间复杂度O(n)，空间复杂度O(n)
    <3> 异或法
    <4> 等差数列求和
    <5> 暴力遍历法
class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
        int left = 0;
        int right = records.size() - 1;

        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid)
            {
                left = mid + 1;
            }

            if(records[mid] > mid)
            {
                right = mid;
            }
        }

        //边界问题，n-1个元素，n个学生，必定有一人缺席，缺席为学号最后一位的学生
        if(left == records.size() - 1 && left == records[left])
        {
            left++;
        }

        return left;
    }
};
  1. 等差数列
class Solution 
{
public:
    int takeAttendance(vector<int>& records) 
    {
        //等差数列求和，首项加末项乘以项数除以2
        int sum = ((0 + records.size()) * (records.size() + 1)) / 2;

        for(int i = 0; i < records.size(); i++)
        {
            sum -= records[i];
        }

        return sum;
    }
};
  1. 哈希表
class Solution 
{
public:
    int takeAttendance(vector<int>& records) 
    {
        //哈希表法
        int n = records.size() + 1;
        int* hash = (int*)malloc(n * sizeof(int));
        //单位字节
        memset(hash, 0, n * sizeof(int));
        int i = 0;
        for(i = 0; i < records.size(); i++)
        {
            hash[records[i]]++;
        }

        for(i = 0; i < n; i++)
        {
            if(hash[i] == 0)
            {
                break;
            }
        }

        return i;
    }
};
  1. 暴力遍历
class Solution 
{
public:
    int takeAttendance(vector<int>& records) 
    {
        //暴力遍历
        int cur = 0;
        while(cur < records.size())
        {
            if(cur != records[cur])
            {
                break;
            }

            cur++;
        }

        if(cur == records.size() - 1 && records[cur] == cur)
        {
            cur++;
        }

        return cur;
    }
};
  1. 异或法
class Solution 
{
public:
    int takeAttendance(vector<int>& records)
    {
        //异或法
        int sum = 0;
        for(int i = 0; i < records.size() + 1; i++)
        {
            sum ^= i;
        }

        for(int i = 0; i < records.size(); i++)
        {
            sum ^= records[i];
        }

        return sum;
    }
};

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

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

相关文章

leetcode精选算法刷题训练篇 之 链表OJ（包含题目链接以及详细讲解）

leetcode精选算法刷题训练篇 之 链表OJ（包含题目链接以及详细讲解）

好好学习&#xff0c;giao哥给你补&#x1f95a; 1、移除链表元素 难度等级&#xff1a;⭐ 题目链接&#xff1a;移除链表元素 2、链表的中间节点 难度等级&#xff1a;⭐⭐ 题目链接&#xff1a;链表的中间节点 3、反转链表 难度等级&#xff1a;⭐⭐⭐ 题目链接&#x…
阅读更多...
C#版开源免费的Bouncy Castle密码库

C#版开源免费的Bouncy Castle密码库

前言 今天大姚给大家分享一款C#版开源、免费的Bouncy Castle密码库&#xff1a;BouncyCastle。 项目介绍 BouncyCastle是一款C#版开源、免费的Bouncy Castle密码库&#xff0c;开发人员可以通过该项目在他们的 C# 应用程序中使用 Bouncy Castle 提供的各种密码学功能&#x…
阅读更多...
git提交代码描述时如何换行（更新时间24/3/12）

git提交代码描述时如何换行（更新时间24/3/12）

问题复现&#xff08;信心满满使用转义字符换行&#xff09; 解决方法&#xff1a; 写多个-m字符串的结构可以实现自动换行 注意空格 git commit -m"第一行描述" -m"第二行描述" 效果演示&#xff1a;&#xff08;强迫症福利&#xff09;
阅读更多...
近700所高校，2024年预算出炉！

近700所高校，2024年预算出炉！

办学经费&#xff0c;是高校发展的核心与基石。学校人才培养、科学研究等各项事业的开展&#xff0c;都有赖于教育经费的支持。 近日&#xff0c;全国已有北京、上海、江苏、浙江等20多个省&#xff08;市、自治区&#xff09;的高校对外公布了2024年预算经费&#xff0c;小编…
阅读更多...
L2-035 完全二叉树的层序遍历（Python）

L2-035 完全二叉树的层序遍历（Python）

L2-035 完全二叉树的层序遍历 分数 25 全屏浏览 切换布局 作者 陈越 单位 浙江大学 一个二叉树&#xff0c;如果每一个层的结点数都达到最大值&#xff0c;则这个二叉树就是完美二叉树。对于深度为 D 的&#xff0c;有 N 个结点的二叉树&#xff0c;若其结点对应于相同深度…
阅读更多...
深入联合文件系统

深入联合文件系统

Union File System&#xff08;联合文件系统&#xff0c;UnionFS&#xff09;是一种轻量级的高性能分层文件系统&#xff0c;它支持将文件系统中的修改信息作为一次提交&#xff0c;并层层叠加&#xff0c;同时可以将不同目录挂载到同一个虚拟文件系统下&#xff0c;应用看到的…
阅读更多...
C# 8.0+版本项目 string不可为空

C# 8.0+版本项目 string不可为空

1.在某一次新建项目的时候发现&#xff0c;新建的项目&#xff0c;写的测试接口&#xff0c;接口的入参有string的参数&#xff0c; 但是调用接口的时候string的参数没有传报了400&#xff0c;很奇怪&#xff0c;也没有语法错误之类的。 2.解决办法 在项目上右键->属性->…
阅读更多...
计算机毕业设计-springboot+vue前后端分离电竞社交平台管理系统部分成果分享

计算机毕业设计-springboot+vue前后端分离电竞社交平台管理系统部分成果分享

4.5系统结构设计 本系统使用的角色主要有系统管理员、顾客、接单员&#xff0c;本系统为后台管理系统&#xff0c;游客用户可以经过账号注册&#xff0c;管理员审核通过后&#xff0c;用账号密码登录系统&#xff0c;查看后台首页&#xff0c;模块管理&#xff08;顾客信息&am…
阅读更多...
Covalent Network (CQT) 通过统一 API 集成，为 Gnosis Chain 的 AI 潜力赋能

Covalent Network (CQT) 通过统一 API 集成，为 Gnosis Chain 的 AI 潜力赋能

作为一个为超 225 个链提供服务的领先多链索引器&#xff0c;Covalent Network (CQT) 正在与知名的 EVM 区块链基础设施提供者 Gnosis Chain 展开一项激动人心的合作。这一战略合作象征着先进的实时数据索引技术的集成&#xff0c;包括 Covalent Network (CQT) 的统一 API 和 G…
阅读更多...
前端入职配置新电脑！！！

前端入职配置新电脑！！！

前端岗位入职第一天到底应该做些什么呢&#xff1f;又该怎样高效的认识、融入团队&#xff1f;并快速进入工作状态呢&#xff1f;这篇文章就来分享一下&#xff0c;希望对即将走向或初入前端职场的你&#xff0c;能够有所帮助。内含大量链接&#xff0c;欢迎点赞收藏&#xff0…
阅读更多...
解决gpt无法发送对话的问题

解决gpt无法发送对话的问题

问题描述 如图&#xff0c;今天登上去发现怎么无法发送消息 解决 可能是cookie问题&#xff0c;重新删除了就行了 cookie删除后&#xff0c;需要重新登录&#xff0c;主题色也重置为原来的白色了
阅读更多...
MQTT Topic通配符

MQTT Topic通配符

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; 往期热门专栏回顾 专栏…
阅读更多...
简单了解一下Linux的文件系统和目录结构

简单了解一下Linux的文件系统和目录结构

前言 这篇技术文章简单探讨了Linux的文件系统和目录结构&#xff0c;通过详细介绍Linux文件系统的组织方式和各个目录的作用&#xff0c;读者将能够更好地理解Linux系统的运作机制&#xff0c;从而提升对系统管理和优化的能力。无论您是初学者还是有经验的Linux用户&#xff0…
阅读更多...
100元就不能投资吗？不可能，WeTrade1招激活

100元就不能投资吗？不可能，WeTrade1招激活

100元就不能投资吗?当然能进行投资了&#xff0c;尤其是现在投资方式多样化&#xff0c;又灵活&#xff0c;简单来说放在支付宝中就行&#xff0c;但是在可以承担风险的前提下想获得更获得更多的收益&#xff0c;WeTrade认为可以通过杠杆实现这个目的。 如果用1:1的杠杆交易&…
阅读更多...
【Python爬虫神器揭秘】手把手教你安装配置Scrapy，高效抓取网络数据

【Python爬虫神器揭秘】手把手教你安装配置Scrapy，高效抓取网络数据

1、 引言 在大数据时代&#xff0c;网络上的信息犹如海洋般浩瀚。想要在这片海洋里挖掘宝藏&#xff0c;一款强大的工具必不可少。今天我们要带大家深入探索的就是Python界鼎鼎大名的爬虫框架——Scrapy。无论你是数据分析师、研究员还是开发者&#xff0c;学会利用Scrapy来自…
阅读更多...
郑州大学2024年3月招新赛题解

郑州大学2024年3月招新赛题解

1.两重二for循环维护次大值 这里我就直接用map维护了&#xff0c;多了个logn复杂度还是可以的&#xff0c;下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace std; int n,a[1010]; map<int,int> mp; int main(){cin>>n;int sum0;map<int,…
阅读更多...
惬意了解 —— 前端发展史

惬意了解 —— 前端发展史

下拉底部&#xff0c;参与投票&#xff5e;&#xff5e; 前端发展史&#xff1a;从洪荒时代到现代 前端开发已经走过了将近20年的历程&#xff0c;从最早的纯静态页面到如今的现代前端框架&#xff0c;我们见证了前端技术的蓬勃发展。让我们一起回顾这段历史。 洪荒时代&…
阅读更多...
git push解决办法：! [remote rejected] prod -＞ prod (pre-receive hook declined)

git push解决办法：! [remote rejected] prod -＞ prod (pre-receive hook declined)

今天想把最近改的东西上传到Gogs上发版一下子的&#xff0c;但是发现有冲突合并不了&#xff0c;于是我切回自己的分支合并了prod&#xff0c;把冲突处理了一下子&#xff0c;还又增加了一点修改&#xff0c;push后.......又回到prod进行git push&#xff0c;哦豁~这就出了问题…
阅读更多...
基于Springboot影城管理系统设计与实现

基于Springboot影城管理系统设计与实现

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…
阅读更多...
【实战项目】Boost搜索引擎项目

【实战项目】Boost搜索引擎项目

目录 1. 项目的相关背景 2. 搜索引擎的相关宏观原理 3. 搜索引擎技术栈和项目环境 4. 正排索引 vs 倒排索引 - 搜索引擎具体原理 4.1 正排索引 4.2 目标文档进行分词 4.3 倒排索引 4.4 模拟一次查找的过程&#xff1a; 5. 编写数据去标签与数据清洗的模块 Parser 5.1…
阅读更多...
最新文章

Copyright @ 2022~2023