力扣中等 33.搜索旋转排序数组

文章目录

  • 题目介绍
  • 题解

题目介绍

在这里插入图片描述
在这里插入图片描述

题解

首先用 153. 寻找旋转排序数组中的最小值 的方法,找到 nums 的最小值的下标 i。

然后分类讨论:

  1. 如果 target>nums[n−1],在 [0,i−1] 中二分查找 target。

  2. 如果 target≤nums[n−1],那么:

    1. 如果 i=0,说明 nums 是递增的,直接在 [0,n−1] 中二分查找 target。

    2. 如果 i>0,那么 target 一定在第二段 [i,n−1] 中,在 [i,n−1] 中二分查找 target。

      这两种情况可以合并成:在 [i,n−1] 中二分查找 target

class Solution {public int search(int[] nums, int target) {int n = nums.length, i = findMin(nums);if (target > nums[n - 1]) { // target 在第一段return lowerBound(nums, 0, i - 1, target); }// target 在第二段return lowerBound(nums, i, n - 1, target); }// 153. 寻找旋转排序数组中的最小值private int findMin(int[] nums) {int left = 0, right = nums.length - 2; // 闭区间 [0, nums.length - 2]while (left <= right) { int mid = left + (right - left) / 2;if (nums[mid] < nums[nums.length - 1]) {right = mid - 1; } else {left = mid + 1;               }}return left;}// 有序数组中找 target 的下标private int lowerBound(int[] nums, int left, int right, int target) {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;}
}```

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

fasterRCNN模型实现飞机类目标检测

加入会员社群&#xff0c;免费获取本项目数据集和代码&#xff1a;点击进入>> 关于python哥团队 我们是一个深度学习领域的独立工作室。团队成员有&#xff1a;中科大硕士、纽约大学硕士、浙江大学硕士、华东理工博士等&#xff0c;曾在腾讯、百度、德勤等担任算法工程师…

Nginx静态资源优化、压缩、缓存处理

一、静态资源优化配置语法 Nginx对静态资源如何进行优化配置。这里从三个属性配置进行优化&#xff1a; sendfile on; tcp_nopush on; tcp_nodeplay on; &#xff08;1&#xff09;sendfile&#xff0c;用来开启高效的文件传输模式。 语法sendfile on |off;默认值sendfile …

【图像检索】基于Gabor特征的图像检索,matlab实现

博主简介&#xff1a;matlab图像代码项目合作&#xff08;扣扣&#xff1a;3249726188&#xff09; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 本次案例是基于Gabor特征的图像检索&#xff0c;用matlab实现。 一、案例背景和算法介绍 这次博…

Java笔试面试题AI答之单元测试JUnit(7)

文章目录 37. 请列举一些JUnit扩展 &#xff1f;1. 参数化测试2. 条件测试执行3. 临时目录4. 时间测试5. 重复测试6. 前置/后置条件7. Mockito8. Spring Test9. JUnit Vintage10. Testcontainers11. 自定义注解和扩展12. 测试监听器&#xff08;TestListener 和 RunListener&am…

2024年数学建模比赛题目及解题代码

目录 一、引言 1. 1竞赛背景介绍 1.1.1数学建模竞赛概述 1.1.2生产过程决策问题在竞赛中的重要性 1.2 解题前准备 1.2.2 工具与资源准备 1.2.3 心态调整与策略规划 二、问题理解与分析 三、模型构建与求解 3.1 模型选择与设计 3.1.1 根据问题特性选择合适的数学模型类…

【永磁同步电机(PMSM)】 4. 坐标变换的 Matlab 仿真

【永磁同步电机&#xff08;PMSM&#xff09;】 4. 坐标变换的 Matlab 仿真 1. Clarke 变换的模型与仿真1.1 Clarke 变换1.2 Clarke 变换的仿真模型 2. Park 变换的模型与仿真2.1 Park 变换2.2 Park 变换的仿真模型 3. Simscape标准库变换模块3.1 abc to Alpha-Beta-Zero 模块3…

更换硬盘后,电脑装完系统进不去?或PE能识别硬盘但开机/启动/BIOS识别不了硬盘解决办法

由于现在的电脑主板&#xff0c;默认都是UEFI启动&#xff0c;硬盘只有使用GUID分区表&#xff0c;主板BIOS才找得到系统引导&#xff01; 而当我们拿到一块新硬盘&#xff0c;使用分区工具默认类型分区&#xff0c;默认是MBR类型&#xff0c;所以这种分区的硬盘&#xff0c;B…

14.面试算法-字符串常见算法题(三)

1. 字符串回文问题 1.1 LeetCode.125. 验证回文串 回文问题在链表中是重点&#xff0c;在字符串中同样是个重点。当初我去美团面试第一轮技术面的第一个算法题就是让写判断字符串回文的问题。 这个本身还是比较简单的&#xff0c;只要先转换成字符数组&#xff0c;然后使用双…

肺结节检测系统源码分享

肺结节检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Visio…

uniapp uview扩展u-picker支持日历期间 年期间 月期间 时分期间组件

uniapp uview扩展u-picker支持日历期间 年期间 月期间 时分期间组件 日历期间、年期间、月期间及时分期间组件在不同的应用场景中发挥着重要的作用。这些组件通常用于表单、应用程序或网站中&#xff0c;以方便用户输入和选择特定的日期和时间范围。以下是这些组件的主要作用&a…

C++:日期类的实现

目录 一、前言 二、头文件 三、各个函数的实现 打印、检查日期及获取日期 、、-、-、 、<、<、>、>、 &#xff01; 日期-日期 >>、<< 一、前言 前面几篇讲了关于类和对象的一些知识&#xff0c;本篇就来实现一下前面用到的日期类。 二、头文…

TryHackMe 第3天 | Pre Security (中)

该学习路径讲解了网络安全入门的必备技术知识&#xff0c;比如计算机网络、网络协议、Linux命令、Windows设置等内容。上一篇中简短介绍了计算机网络相关的知识&#xff0c;本篇博客将记录 网络协议 部分。 How the web works? DNS in detail DNS (Domain name system&…

Java面试篇-AOP专题(什么是AOP、AOP的几个核心概念、AOP的常用场景、使用AOP记录操作日志、Spring中的事务是如何实现的)

文章目录 1. 什么是AOP2. AOP的几个核心概念3. AOP的常用场景4. 使用AOP记录操作日志4.1 准备工作4.1.1 引入Maven依赖4.1.2 UserController.java4.1.3 User.java4.1.4 UserService.java 4.2 具体实现&#xff08;以根据id查询用户信息为例&#xff09;4.2.1 定义切面类&#x…

SkyWalking 环境搭建部署

架构简介 skywalking agent : 和业务系统绑定在一起,负责收集各种监控数据skywalking oapservice : 是负责处理监控数据的,比如接受skywalking agent的监控数据,并存储在数据库中;接受skywalking webapp的前端请求,从数据库查询数据,并返回数据给前端。Skywalking oapserv…

华为HarmonyOS地图服务 7- 在地图上绘制标记

场景介绍 本章节将向您介绍如何在地图的指定位置添加标记以标识位置、商家、建筑等。 点标记用来在地图上标记任何位置,例如用户位置、车辆位置、店铺位置等一切带有位置属性的事物。Map Kit提供的点标记功能(又称 Marker)封装了大量的触发事件,例如点击事件、长按事件、…

【RabbitMQ】消息分发、事务

消息分发 概念 RabbitMQ队列拥有多个消费者时&#xff0c;队列会把收到的消息分派给不同的消费者。每条消息只会发送给订阅该队列订阅列表里的一个消费者。这种方式非常适合扩展&#xff0c;如果现在负载加重&#xff0c;那么只需要创建更多的消费者来消费处理消息即可。 默…

linux网络编程5

24.9.21学习目录 一.TCP1.TCP流程2.TCP相关函数3.三次握手 一.TCP 1.TCP流程 服务器流程&#xff1a; 创建套接字socket&#xff08;&#xff09;将套接字与服务器网络信息结构体绑定bind&#xff08;&#xff09;将套接字设置为监听状态listen&#xff08;&#xff09;阻塞等…

进程间的通信4 共享内存

共享内存 1.共享内存简介 共享内存是将分配的物理空间直接映射到进程的用户虚拟地址空间中&#xff0c;减少数据在内核空间缓存共享内存是一种效率较高的进程间通讯的方式在 Linux 系统中通过 ipcs -m 查看所有的共享内存 共享内存模型图 2.共享内存的创建 1.函数头文件 #…

Java算法专栏

专栏导读 在当今这个技术日新月异的时代&#xff0c;Java算法作为软件开发的核心&#xff0c;对于提升程序性能和解决复杂问题至关重要。本“Java算法”专栏旨在帮助读者深入理解Java编程语言中的算法原理和应用&#xff0c;通过实战案例和深入分析&#xff0c;使读者能够掌握…

Java汽车销售管理

技术架构&#xff1a; springboot mybatis Mysql5.7 vue2 npm node 功能描述&#xff1a; 针对汽车销售提供客户信息、车辆信息、订单信息、销售人员管理、财务报表等功能&#xff0c;提供经理和销售两种角色进行管理 效果图&#xff1a;