【优选算法】——二分查找!

目录

1、二分查找

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

3、搜索插入位置

4、x的平方根

5、山脉数组的封顶索引

6、寻找峰值 

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

8、点名

9、完结散花


1、二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

题解:这个题目我们只要用到朴素版的二分查找算法即可!

解题代码:

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

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

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

解题代码:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1,-1};//处理边界情况
        vector<int> ret;
        int left=0,right=nums.size()-1;
        //求左端点
        while(left<right)//判断条件一定是<,如果<=则会进入死循环
        {
            int mid=left+(right-left)/2;//不能加1,否则死循环
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }
        ret.push_back(nums[right]==target?right:-1);
        //求右端点
        left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;//一定要加1,否则死循环
            if(nums[mid]>target) right=mid-1;
            else left=mid;
        }
        ret.push_back(nums[left]==target?left:-1);
        return ret;
    }
};

3、搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

解题代码: 

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) right= mid;
            else left=mid+1;
        }
        return nums[left]<target?left+1:left;
    }
};

4、x的平方根

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

解题代码:

class Solution {
public:
    int mySqrt(int x) {
        //求右端点
        long long left=0,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;
    }
};

5、山脉数组的封顶索引

给定一个长度为 n 的整数 山脉 数组 arr ,其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1:

输入:arr = [0,1,0]
输出:1

示例 2:

输入:arr = [0,2,1,0]
输出:1

示例 3:

输入:arr = [0,10,5,2]
输出:1

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

6、寻找峰值 

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1:

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5 
解释:你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

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

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

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size()-1;
        //处理特殊情况,即未发生旋转,或旋转到原数组
        if(nums[0]<nums[n]) return nums[0];
        int left=0,right=n;
        //求最左端点
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[0]) right=mid;
            else left=mid+1;
        }
        return nums[left];
    }
};

8、点名

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席,请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

class Solution {
public:
    int takeAttendance(vector<int>& r) {
        int end=r.size()-1;
        //特殊情况处理
        if(r[end]==end) return end+1;
        int left=0,right=end;
        //求最左端点的二分查找
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(r[mid]>mid) right=mid;
            else left=mid+1;
        }
        return right;
    }
};

其他解法: 

>hash映射

class Solution {
public:
    int takeAttendance(vector<int>& r) {
        int n=r.size()+1;
        int hash[10000]={0};
        for(auto e:r) hash[e]++;
        for(int i=0;i<n;i++) 
        {
            if(hash[i]==0)
            return i;
        }
        return n;
    }
};

>位运算

class Solution {
public:
    int takeAttendance(vector<int>& r) {
        int ret=0;
        for(int i=0;i<r.size();i++)
        {
            ret^=r[i];
            ret^=i;
        }
        return ret^=r.size();
    }
};

>暴力查找

class Solution {
public:
    int takeAttendance(vector<int>& r) {
        int ret=0;
        for(int i=0;i<r.size();i++)
        {
            if(r[i]!=i) return i;
        }
        return r.size();
    }
};

>数学(高斯求和公式)

class Solution {
public:
    int takeAttendance(vector<int>& r) {
        int ret=0,sum1=0,sum2=0;
        for(int i=0;i<r.size();i++)
        {
            sum1+=r[i];
            sum2+=i;
        }
        return sum2-sum1+r.size();
    }
};

9、完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

​​​​

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

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

相关文章

Fooocus图像生成软件本地部署教程:在Windows上快速上手AI创作

文章目录 前言1. 本地部署Fooocus图像生成软件1.1 安装方式1.2 功能介绍 2. 公网远程访问Fooocus3. 固定Fooocus公网地址 前言 本篇文章将介绍如何在本地Windows11电脑部署开源AI生图软件Fooocus&#xff0c;并结合Cpolar内网穿透工具轻松实现公网环境远程访问与使用。 Foooc…

elasticSearch 7.12.1 Docker 安装ik分词

一、下载 https://github.com/infinilabs/analysis-ik/releases/tag/v7.12.1 将文件解压&#xff0c;复制到docker挂载的目录 docker ps#重启docker docker restart f7ec58e91f1f 测试 GET _analyze?pretty {"analyzer": "ik_max_word","text&qu…

智慧汇聚:十款企业培训工具打造学习型企业

在当今快速变化的商业环境中&#xff0c;企业要想保持竞争力&#xff0c;就必须不断适应新技术、新市场和新的工作方式。构建一个学习型企业&#xff0c;不仅能够促进员工的个人成长&#xff0c;还能增强团队的整体能力和企业的创新能力。为了实现这一目标&#xff0c;借助先进…

【Searxng】Searxng docker 安装

SearXNG将用户的查询请求分发至多个支持的搜索引擎&#xff0c;并收集返回的结果进行汇总处理。在这个过程中&#xff0c;它通过内置的过滤器功能屏蔽广告和其他不相关内容&#xff0c;确保搜索结果的纯净度。 一键部署 docker run \--name searxng \-p ????:8080 \-v ~/s…

FastAPI 请求体解析:基础概念与综合应用

FastAPI 请求体解析&#xff1a;基础概念与综合应用 本文深入探讨了 FastAPI 中的请求体概念&#xff0c;强调使用 Pydantic 模型来声明请求体数据结构。通过具体示例&#xff0c;展示了如何定义请求体、可选参数及默认值&#xff0c;提升数据验证和类型提示的便利性。文章还说…

Linux下的Debugfs

debugfs 1. 简介 类似sysfs、procfs&#xff0c;debugfs 也是一种内存文件系统。不过不同于sysfs一个kobject对应一个文件&#xff0c;procfs和进程相关的特性&#xff0c;debugfs的灵活度很大&#xff0c;可以根据需求对指定的变量进行导出并提供读写接口。debugfs又是一个Li…

【论文速读】Optimization-based Prompt Injection Attack to LLM-as-a-Judge

基于优化的提示词注入攻击 摘要引言问题描述LLM-as-a-judge威胁模型攻击者知道什么 JUDGEDECEIVER 细节概述生成影子候选回复公式化为优化问题Target-aligned generation lossTarget-enhancement lossAdversarial perplexity loss优化问题 求解优化问题 摘要 LLM-as-a-Judge 利…

单智能体carla强化学习实战工程介绍

有三个工程&#xff1a; Ray_Carla: 因为有的论文用多进程训练强化学习&#xff0c;包括ray分布式框架等&#xff0c;这里直接放了一个ray框架的示例代码&#xff0c;是用sac搭建的&#xff0c;obs没用图像&#xff0c;是数值状态向量值&#xff08;速度那些&#xff09;。 …

PD取电快充协议芯片,XSP08Q在灯具中的应用

前言 随着快充技术不断的发展 USB Type-C端口的普及 PD快充成了电子设备中的宠儿&#xff0c;在各种电子设备领域都能见到PD快充的身影&#xff0c;不得不说快充技术的出现让电子设备在充电的速度上得到前所未有的体验&#xff0c;大大的缩短了设备的充电时间。快充协议芯片不…

【AI开源项目】Botpress - 开源智能聊天机器人平台及其部署方案

文章目录 Botpress 概述Botpress 的定位 Botpress 的主要特点1. OpenAI 集成2. 易于使用3. 定制和扩展性4. 多平台支持5. 集成和扩展 API6. 活跃的社区和详尽的文档 部署方案集成集成开发集成部署机器人示例开发工具代理本地开发先决条件从源代码构建 Botpress 如何解决常见问题…

【天线&运输】交通事故严重程度检测系统源码&数据集全套:改进yolo11-HSFPN

改进yolo11-ASF-DySample等200全套创新点大全&#xff1a;交通事故严重程度检测系统源码&#xff06;数据集全套 1.图片效果展示 项目来源 人工智能促进会 2024.11.01 注意&#xff1a;由于项目一直在更新迭代&#xff0c;上面“1.图片效果展示”和“2.视频效果展示”展示的系…

使用 Elastic、OpenLLMetry 和 OpenTelemetry 跟踪 LangChain 应用程序

作者&#xff1a;来自 Elastic Bahubali Shetti Langchain 应用程序的使用正在增长。构建基于 RAG 的应用程序、简单的 AI 助手等的能力正在成为常态。观察这些应用程序更加困难。考虑到现有的各种选项&#xff0c;本博客展示了如何将 OpenTelemetry 检测与 OpenLLMetry 结合使…

揭秘Scam-as-a-Service:警惕钓鱼攻击的产业化

2024年6月开始&#xff0c;CertiK安全团队监控到大量相似的phishing/drainer transaction&#xff0c;仅6月份监控到的涉案金额就超过5500万美元&#xff0c;进入8、9月份后&#xff0c;相关钓鱼地址的活动更加频繁&#xff0c;钓鱼攻击有愈演愈烈的架势。整个2024年第三季度&a…

前端Election

一.什么是Election 1.一款应用广泛的跨平台和桌面应用开发框架。 2.本质 Election的本质是结合了Chromium与Node.js 3.构建 使用HTML ,CSS,JS等Web技术构建桌面应用程序。 只要最后能转换成html css js即可 二.流程模型 1.主进程 关于node.js的任何api都在这里调用 一个纯…

如何在Linux系统中使用SSH进行安全连接

如何在Linux系统中使用SSH进行安全连接 SSH简介 安装SSH 在Debian/Ubuntu系统中安装 在CentOS/RHEL系统中安装 启动SSH服务 验证SSH是否安装成功 SSH配置 配置监听端口 配置登录方式 SSH客户端 安装SSH客户端 使用SSH客户端 SSH密钥认证 生成SSH密钥对 复制公钥到远程服务器…

SpringBoot源码解析(一)

SpringBoot自动装配原理 SpringBootApplication注解 我们在使用SpringBoot时&#xff0c;通常使用的是SpringBootApplication这个注解&#xff0c;比如&#xff1a; 而这个注解的定义为下图&#xff0c;可以发现这个注解上有另外三个注解&#xff1a;SpringBootConfiguration…

BES2600WM---HiLink RM56 EVK

0 Preface/Foreword 0.1 路径 OpenHarmony/device_soc_bestechnic - 码云 - 开源中国 https://github.com/Hi-LinkDuino/RM56 1 环境搭建 1.1 安装依赖工具 sudo apt-get install build-essential gcc g make zlib* libffi-dev e2fsprogs pkg-config flex bison perl bc ope…

C# 编程语言学习教程

C# 编程语言学习教程 目录 C# 简介 1.1 什么是 C#1.2 C# 的特点1.3 C# 的应用领域 环境搭建 2.1 安装 Visual Studio2.2 创建第一个 C# 项目 基础语法 3.1 数据类型3.2 控制结构3.3 数组与字符串 面向对象编程 4.1 类与对象4.2 继承与多态4.3 接口与抽象类 常用库与框架 5.1 .…

PAT甲级-1092 To Buy or Not to Buy

题目 题目大意 Eva想要买珠子&#xff0c;但是只能按串买。如果串上有她想要买的所有珠子&#xff0c;那么输出“Yes”&#xff0c;再输出需要额外买几个珠子。如果串上缺少她想要的珠子&#xff0c;那么输出“No”&#xff0c;并输出缺少的珠子个数。其中&#xff0c;s1是商店…

使用WebAssembly优化Web应用性能

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用WebAssembly优化Web应用性能 引言 WebAssembly 简介 编译 WebAssembly 模块 使用 Emscripten 编译 C/C 代码 使用 Rust 编译…