【二分】搜索旋转数组
文章目录
- 不重复数组找最小值,返回下标
- 重复数组找最小值,返回下标
- 不重复数组找target,返回下标
- 重复数组找target,返回bool
- 重复数组找target,返回下标
不重复数组找最小值,返回下标


class Solution {public int findMin(int[] nums) {int n = nums.length;int l = 0;int r = n - 1;while(l <= r){if(l == r || nums[l] < nums[r]){break;}int mid = l + (r - l) / 2;if(nums[mid] >= nums[l]){// [l, mid]有序l = mid + 1;}else{// [mid, r]有序r = mid;}}return nums[l];}
}
class Solution {public int findMin(int[] nums) {int n = nums.length;int l = 0;int r = n - 1;while(l <= r){if(l == r || nums[l] <= nums[r]){// [l,r]已经有序break;}int mid = l + (r - l) / 2;if(nums[mid] > nums[l]){l = mid + 1;}else if(nums[mid] < nums[l]){r = mid;}else{l++;}}return nums[l];}
}
重复数组找最小值,返回下标


nums[mid] < nums[l],说明最小值肯定在(low, mid]区间内,则r = mid

nums[mid] > nums[l],说明最小值肯定在mid右侧,(mid,r]区间内,则l = mid + 1

nums[mid] == nums[l],无法判断最小值在哪个区间,但一定在(l, r]内部
我们假设nums[l]、nums[mid]就是最小值,那我们可以排除l,即l++,因为nums[mid]可以替代nums[l]
若nums[l]、nums[mid]不是最小值,我们直接l++
寻找旋转排序数组中的最小值 II
class Solution {public int findMin(int[] nums) {int n = nums.length;int l = 0;int r = n - 1;while(l <= r){if(l == r || nums[l] <= nums[r]){// [l,r]已经有序break;}int mid = l + (r - l) / 2;if(nums[mid] > nums[l]){l = mid + 1;}else if(nums[mid] < nums[l]){r = mid;}else{l++;}}return nums[l];}
}
不重复数组找target,返回下标

class Solution {public int search(int[] nums, int target) {int n = nums.length;int l = 0;int r = n - 1;while(l <= r){int mid = l + (r - l) / 2;if(target == nums[mid]){return mid;}if(nums[mid] > nums[l]){// [l, mid]有序if(target >= nums[l] && target < nums[mid]){// 在有序区间内r = mid - 1;}else{l = mid + 1; }}else if(nums[mid] < nums[l]){// [mid, r]有序if(target > nums[mid] && target <= nums[r]){// 在有序区间内l = mid + 1;}else{r = mid - 1; }}else{l++;}}return -1;}
}
重复数组找target,返回bool

class Solution {public int search(int[] nums, int target) {int n = nums.length;int l = 0;int r = n - 1;while(l <= r){int mid = l + (r - l) / 2;if(target == nums[mid]){return mid;}if(nums[mid] > nums[l]){// [l, mid]有序if(target >= nums[l] && target < nums[mid]){// 在有序区间内r = mid - 1;}else{l = mid + 1; }}else if(nums[mid] < nums[l]){// [mid, r]有序if(target > nums[mid] && target <= nums[r]){// 在有序区间内l = mid + 1;}else{r = mid - 1; }}else{l++;}}return -1;}
}
重复数组找target,返回下标

class Solution {public int search(int[] nums, int target) {int l = 0;int r = nums.length - 1;if (r == -1)return -1;while (l < r) { // 循环结束条件l==rint mid = l + (r - l) / 2;if (nums[l] < nums[mid]) { // 如果左值小于中值,说明左边区间升序 if (nums[l] <= target && target <= nums[mid]) { // 如果目标在左边的升序区间中,右边界移动到midr = mid;} else { // 否则目标在右半边,左边界移动到mid+1l = mid + 1;}} else if (nums[l] > nums[mid]) { // 如果左值大于中值,说明左边不是升序,右半边升序if (nums[l] <= target || target <= nums[mid]) { // 如果目标在左边,右边界移动到midr = mid;} else { // 否则目标在右半边,左边界移动到mid+1l = mid + 1;}} else if (nums[l] == nums[mid]) { // 如果左值等于中值,可能是已经找到了目标,也可能是遇到了重复值if (nums[l] != target) { // 如果左值不等于目标,说明还没找到,需要逐一清理重复值。l++;} else { // 如果左值等于目标,说明已经找到最左边的目标值 r = l; // 将右边界移动到l,循环结束}}}return (nums[l] == target) ? l : -1; // 返回l,或者-1}
}
相关文章:
【二分】搜索旋转数组
文章目录 不重复数组找最小值,返回下标重复数组找最小值,返回下标不重复数组找target,返回下标重复数组找target,返回bool重复数组找target,返回下标 不重复数组找最小值,返回下标 class Solution {public …...
APSIM模型应用与参数优化、批量模拟
APSIM (Agricultural Production Systems sIMulator)模型是世界知名的作物生长模拟模型之一。APSIM模型有Classic和Next Generation两个系列模型,能模拟几十种农作物、牧草和树木的土壤-植物-大气过程,被广泛应用于精细农业、水肥管理、气候变化、粮食安…...
QT使用QXlsx实现对Excel sheet的相关操作 QT基础入门【Excel的操作】
准备:搭建环境引用头文件QT中使用QtXlsx库的三种方法 QT基础入门【Excel的操作】_吻等离子的博客-CSDN博客 #include "xlsxdocument.h"QTXLSX_USE_NAMESPACE // 添加Xlsx命名空间(https://github.com/dbzhang800/QtXlsxWriter) or QXLSX_USE_NAMESPACE // 添加Xl…...
ARM DIY(四)WiFi 调试
文章目录 焊接打开内核编译选项重新编译内核烧录 && 运行 && 测试完善脚本测速手搓天线正式天线 焊接 换个粗点的风枪嘴,让热风覆盖 RTL8823BS 整体模块,最终实现自动归位 焊接 SDIO 接口的上拉电阻以及复位引脚上拉电阻 硬件部分就这…...
AIGC ChatGPT 实现动态多维度分析雷达图制作
雷达图在多维度分析中是一种非常实用的可视化工具,主要有以下优势: 易于理解:雷达图使用多边形或者圆形的形式展示多维度的数据,直观易于理解。多维度对比:雷达图可以在同一张图上比较多个项目或者实体在多个维度上的…...
Vue2向Vue3过度核心技术路由
目录 1 路由介绍1.思考2.路由的介绍3.总结 2 路由的基本使用1.目标2.作用3.说明4.官网5.VueRouter的使用(52)6.代码示例7.两个核心步骤8.总结 3 组件的存放目录问题1.组件分类2.存放目录3.总结 4 路由的封装抽离5 Vue路由-重定向1.问题2.解决方案3.语法4…...
ElasticSearch常用方法
ElasticSearch:是一个储存、检索、数据分析引擎。 在互联网项目中我们经常会按一定的条件去索引我们指定的数据,但是在大量的数据中我们如果直接查询数据库效率是非常低的,ElasticSearch就可以很好的帮我们完成检索。 es封装了api提供给我我们直接操作…...
nginx下添加http_ssl_module并且配置域名,指定端口
1.切换到源码包: cd /home/nginx-1.23.1 2.进行编译: ./configure --prefix/usr/local/nginx --with-http_stub_status_module --with-http_ssl_module 3.配置完成后,运行命令: make make命令执行后,不要进行mak…...
【PHP】PHP变量
1、变量介绍 PHP 是一门弱类型语言,不必向 PHP 声明该变量的数据类型。PHP 会根据变量的值,自动把变量转换为正确的数据类型。在强类型的编程语言中,必须在使用变量前先声明(定义)变量的类型和名称。 <?php $x5;…...
KVM创建虚拟机可访问外网+可使用Xshell等工具连接
创建虚拟机时使用桥接网络模块即可,如下: 1、创建一个存储卷(虚拟机的磁盘) 2、创建虚拟机时选择网络 3、系统安装完成后配置固定IP地址 vi /etc/sysconfig/network-scripts/ifcfg-eth0ONBOOTyes BOOTPROTOstatic IPADDR16.32.15.60 GATEWAY16.32.15.2…...
数据库——Redis 没有使用多线程?为什么不使用多线程?
文章目录 Redis6.0 之后为何引入了多线程? 虽然说 Redis 是单线程模型,但是, 实际上,Redis 在 4.0 之后的版本中就已经加入了对多线程的支持。 不过,Redis 4.0 增加的多线程主要是针对一些大键值对的删除操作的命令&a…...
Node.JS教程
文章目录 Node.JSNode.js学习指南一、Node.js基础1.认识Node.js2.开发环境搭建3. 模块、包、commonJS3.1、为什么要有模块化开发?3.2、CommonJS规范3.3、 modules模块化规范写法 4.Npm&Yarn4.1、npm使用4.2、全局安装nrm4.3、yarn使用 持续更新中总结 Node.JS N…...
mysql表锁死怎么办?事务锁sql超时被锁死怎么办?
不要慌!不要慌!两句命令教你做人 一、mysql表锁死 1、查询所有进程: SHOW PROCESSLIST; 2、找到进程号kill掉 kill 3269987 2、事务锁 sql超时被锁死 1、查询所有执行中的sql select t.*,to_seconds(now())-to_seconds(t.trx_started) id…...
基于JSP+Servlet+mysql学生宿舍管理系统
基于JSPServletmysql学生宿舍管理系统 一、系统介绍二、功能展示四、其它1.其他系统实现五.获取源码 一、系统介绍 项目类型:Java web项目 项目名称:基于JSPServlet的学生宿舍管理系统[sushe] 项目架构:B/S架构 开发语言:Java…...
Enabling Large Language Models to Generate Text with Citations
本文是LLM系列的文章,针对《Enabling Large Language Models to Generate Text with Citations》的翻译。 使大语言模型能够生成带有引用的文本 摘要1 引言2 任务设置和数据集3 自动评估4 建模5 实验6 人类评估7 相关工作8 结论不足 摘要 大型语言模型(…...
Qt Qml实现仪表盘动画
Qt Qml代码实现的仪表盘动画 效果: Qt Qml 仪表盘动画 Qt Qml 代码实现仪表盘动画 Qt Qml 仪表盘动画 部分Qml代码: import QtQuick 2.0Item {width: 2 * radiusheight: 2 * radiusrequired property double radiusproperty double airspeed: 0propert…...
一次PostgreSQL复杂jsonb数据矫正过程分享
背景介绍 想看干货直接看最后的总结,其他流水账可以不看,也可以当故事看。 7月底我司某产品因故需要拉齐现场版本,其中某地版本较低,且曾经做过一些定制内容,升级前也未识别该情况,导致后续持续一个月不断…...
如何在App里拉起小程序?
什么是小程序运行时框架? FinClip 的小程序编程模型是分为多个页面,每个页面有自己的 template、CSS 和 JS,实际在运行的时候,业务逻辑的 JS 代码是运行在独立的 JavaScript 引擎中,每个页面的 template 和 CSS 是运行…...
函数式编程-Stream流学习第二节-中间操作
1 Stream流概述 java8使用的是函数式编程模式,如同它的名字一样,它可以用来对集合或者数组进行链状流式操作,让我们更方便的对集合或者数组进行操作。 2 案例准备工作 我们首先创建2个类一个作家类,一个图书类 package com.stream.model;…...
SpringCloud 教程 | 第一篇: 服务的注册与发现(Eureka)
一、spring cloud简介 spring cloud 为开发人员提供了快速构建分布式系统的一些工具,包括配置管理、服务发现、断路器、路由、微代理、事件总线、全局锁、决策竞选、分布式会话等等。它运行环境简单,可以在开发人员的电脑上跑。另外说明spring cloud是基…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...
