当前位置: 首页 > news >正文

二分查找旋转数组

已知整数数组nums,先按升序排序后,再旋转。旋转k位后,元素分别为nums[k],nums[k+1]...nums[0]...nums[k-1]。请查找target 是否存在,如果存在返回所在索引;否则返回-1。假定nums没有重复的元素。

假定排序后的数组为{1,2,3,4,5}。

旋转0位:不变。

旋转1位:{2,3,4,5,1}

旋转2位:{3,4,5,1,2}

旋转3位:{4,5,1,2,3}

旋转4位:{5,1,2,3,4}

解题思路

观察后,可以得到如下结论:

旋转数组,可以拆分成左右两个升序数组,且左数组的任意元素都大于右数组的任意元素。

分两步:

  • 找到数组的分界线RBegin,[0,RBegin)是左数组,[RBegin,n)是右数组。特殊情况:只有一个升序数组,则RBegin为0,左数组为空。
  • 如果是小于等于nums.back(),在右边找;否则在左边找。升序寻找元素之前已经讲过了,就不累赘了。
            1. 寻找RBegin

nums[mid] < nums.back()

扔掉右边,不扔mid

nums[mid] == nums.back()

扔掉右边,不扔mid

nums[mid] > nums.back()

扔掉左边,扔掉mid

故用左开右闭空间。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int rBegin = FindRBegin(nums);
        if (target <= nums.back())
        {
            return Find(nums, rBegin, nums.size(), target);
        }
        return Find(nums, 0, rBegin, target);
    }
    int FindRBegin(const vector<int>& nums)
    {
        int left = -1, r = nums.size()-1;//左开右闭
        while (r - left > 1)
        {
            const int mid = left + (r - left) / 2;
            if (nums[mid] <= nums.back())
            {
                r = mid;
            }
            else
            {
                left = mid;
            }
        }
        return r;
    }
    int Find(const vector<int>& nums, int left, int r, int target)
    {
        while (r - left > 1)
        {
            const auto mid = left + (r - left) / 2;
            if (nums[mid] <= target)
            {
                left = mid;
            }
            else
            {
                r = mid;
            }
        }
        return (target == nums[left]) ? left : -1;
    }
};
int main()
{
    vector<int> vNums = {1,2,3,4,6};
    auto res = Solution().search(vNums, 4);
    std::cout << "index:" <<  res;
    if (-1 != res)
    {
        std::cout << " value:" << vNums[res];
    }
}

注意

开发及测试操作系统:Windows10(安装的时候没注意,安装成了英文版)
开发及测试环境:Microsoft Visual Studio 2022  
如果还不明白,请看我的视频;如果看完视频,还是不明白,请下载源码后,直接修改。
 

相关文章:

二分查找旋转数组

已知整数数组nums&#xff0c;先按升序排序后&#xff0c;再旋转。旋转k位后&#xff0c;元素分别为nums[k],nums[k1]...nums[0]...nums[k-1]。请查找target 是否存在&#xff0c;如果存在返回所在索引&#xff1b;否则返回-1。假定nums没有重复的元素。 假定排序后的数组为{1…...

关于3D位姿旋转

一. 主动旋转和被动旋转 1. active rotation 主动旋转 站在坐标系的位置看旋转目标物&#xff1a;目标物主动发生旋转。 2. passive rotation 被动旋转 站在旋转目标物的位置看坐标系&#xff1a; 坐标系发生旋转&#xff0c;相当于目标物在坐标系内的位置被动地发生了旋转…...

解锁项目成功的关键:项目经理的结构化思维之道

1. 项目经理的核心职责 作为项目经理&#xff0c;我们的工作不仅仅是跟踪进度和管理团队。我们的角色在整个项目生命周期中都是至关重要的&#xff0c;从初始概念到最终交付。以下是项目经理的几个核心职责&#xff1a; 确保项目目标的清晰性项目的成功在很大程度上取决于其目…...

力扣974被K整除的子数组

同余定理 使用前缀和哈希表 由于可能是负数所以要进行修正&#xff1a;(sum%kk)%k class Solution { public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0 % k] 1; //0 这个数的余数int sum 0, ret 0;for(auto x…...

简单认识Docker数据管理

文章目录 为何需要docker数据管理数据管理类型 一、数据卷二、数据卷容器三、容器互联 为何需要docker数据管理 因为数据写入后如果停止了容器&#xff0c;再开启数据就会消失&#xff0c;使用数据管理的数据卷挂载&#xff0c;实现了数据的持久化&#xff0c;重启数据还会存在…...

UDP数据报结构分析(面试重点)

在传输层中有UDP和TCP两个重要的协议&#xff0c;下面将针对UDP数据报的结构进行分析 UDP结构图示 UDP报头结构的分析 UDP报头有4个属性&#xff0c;分别是源端口&#xff0c;目的端口&#xff0c;UDP报文长度&#xff0c;校验和&#xff0c;它们都占16位2个字节&#xff0c;所…...

【Java 动态数据统计图】动态数据统计思路案例(动态,排序,数组)二(113)

需求&#xff1a; 有一个List<Map<String.Object>>,存储了区域的数据&#xff0c; 数据是根据用户查询条件进行显示的&#xff1b;所以查询的数据是动态的&#xff1b;按区域维度统计每个区域出现的次数&#xff0c;并且按照次数的大小排序&#xff08;升序&#…...

C++进阶 类型转换

本文简介&#xff1a;介绍C中类型转换的方式 类型转换 C语言中的类型转换为什么C需要四种类型转换C强制类型转换static_castreinterpret_castconst_castdynamic_cast RTTI&#xff08;了解&#xff09;总结 C语言中的类型转换 在C语言中&#xff0c;如果赋值运算符左右两侧类型…...

Idea中隐藏指定文件或指定类型文件

Setting ->Editor ->Code Style->File Types → Ignored Files and Folders输入要隐藏的文件名&#xff0c;支持*号通配符回车确认添加...

第2步---MySQL卸载和图形化工具展示

第2步---MySQL卸载和图形化工具展示 1.MySQL的卸载 2.MySQL的图形化工具 2.1常见的图形化工具 SQLyog&#xff1a;简单。SQLyog首页、文档和下载 - MySQL 客户端工具 - OSCHINA - 中文开源技术交流社区 Mysql Workbench &#xff1a;MySQL :: MySQL Workbench DataGrip&…...

原型和原型链

好久没记了有点忘记了&#xff0c;来记录一下。 1、函数和对象的关系&#xff1a;对象都是通过函数创建的&#xff0c;函数也是一个对象。 2、原型和原型链 1.原型&#xff1a;原型分为两种 prototype&#xff1a;每一个函数都会有prototype属性&#xff0c;它指向函数的原型…...

解决ios隔空播放音频到macos没有声音的问题

解决ios隔空播放音频到macos没有声音的问题 一、检查隔空播放支持设备和系统要求二、打开隔空播放接收器三、重置MAC控制中心进程END 一、检查隔空播放支持设备和系统要求 Mac、iPhone、iPad 和 Apple Watch 上“连续互通”的系统要求 二、打开隔空播放接收器 ps;我设备是同一…...

LTPP在线开发平台【使用教程】

LTPP在线开发平台 点击访问 LTPP在线开发平台 LTPP&#xff08;Learning teaching practice platform&#xff09;在线开发平台是一个编程学习网站&#xff0c;该网站集文章学习、短视频、在线直播、代码训练、在线问答、在线聊天和在线商店于一体&#xff0c;专注于提升用户编…...

0818 新增码表 git拉取代码

目的是新增两个码表字段。然后和前端联调。 use db; delete from sys_dict_data where dict_type res_switch_status; INSERT INTO sys_dict_data VALUES (0, 1, 已接入, 1, res_switch_status, NULL, default, N, 0, , 2022-07-26 10:43:41, , NULL, NULL); INSERT INTO sys…...

AI 绘画Stable Diffusion 研究(十)sd图生图功能详解-精美二维码的制作

免责声明: 本案例所用安装包免费提供&#xff0c;无任何盈利目的。 大家好&#xff0c;我是风雨无阻。 为了让大家更直观的了解图生图功能&#xff0c;明白图生图功能到底是干嘛的&#xff0c;能做什么事情&#xff1f;今天我们继续介绍图生图的实用案例-精美二维码的制作。 对…...

C# File.ReadAllLines()报错

项目中需要读取一个文本文件的内容&#xff0c;调用C#的File.ReadAllLines(path)方法&#xff0c;但是报错&#xff0c;就提示unknown exception&#xff0c;也没其他提示了。 文件是在的&#xff0c;并且&#xff0c;如果把文件拷贝到另外一个路径&#xff0c;再次读取是正常…...

LeetCode 1162. As Far from Land as Possible【多源BFS】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

【算法】二分查找(整数二分和浮点数二分)

二分查找也称折半查找&#xff08;Binary Search&#xff09;&#xff0c;是一种效率较高的查找方法&#xff0c;时间复杂度为O(logN)。 二分查找采用了“分治”策略。使用二分查找时&#xff0c;数组中的元素之间得有单调性&#xff08;升序或者降序&#xff09;。 二分的模…...

git压缩/合并多次commit提交为1次commit提交

git压缩/合并N次commit提交为1次commit提交 假设有最近3次提交&#xff1a; commit_id1 commit_id2 commit_id3目标是把以上3次commit合并成1个commit&#xff0c;注意&#xff0c;最新的commit提交在最上面。 在git bash里面的操作步骤&#xff1a; &#xff08;1&#xff0…...

【3519DV500】AI算法承载硬件平台_2.5T算力+AI ISP图像处理_超感光视频硬件方案开发

Hi3519DV500 内置双核 A55 &#xff0c;提供高效、丰富和灵活的CPU 资源&#xff0c;以满足客户计算和控制需求。 Hi3519DV500集成了高效的神经网络推理引擎&#xff0c;最高2.5Tops NN算力&#xff0c;支持业界主流的神经 网络框架。神经网络支持完整的 API 和工具链&#xf…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...