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

33. 搜索旋转排序数组-二重二分查找

33. 搜索旋转排序数组-二分查找

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

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

示例 1:

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

示例 2:

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

示例 3:

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

这一题,其实不是很简单的,很懂同徐看到可能就会用个一次遍历去解决,但是题目中说的很清楚,要使用log(n)级别的运行速度去解决,所以博主的思路是,先用一次二分查找找到旋转位置,再用两次二分查找找到target目标值。
解题代码如下:

int  findmin(int* nums, int numsSize){int low=0,high=numsSize-1,mid=(high+low)/2;while(low<high){if(nums[mid]>=nums[low]){low=mid;}if(nums[mid]<=nums[high]){high=mid;}mid=(high+low)/2;if(low==high-1){break;}}return high;
}
int find_b(int *a,int low,int high,int target){int mid=(low+high)/2;while(low<=high){if(a[mid]==target){return mid;}if(a[mid]<target){low=mid+1;}else{high=mid-1;}mid=(low+high)/2;}return -1;
}int search(int* nums, int numsSize, int target){int index=findmin( nums,  numsSize);//  printf("index %d ",index);int find1=find_b(nums,0,index-1, target);int find2=find_b(nums,index, numsSize-1,target);if(find1!=-1){return find1;}if(find2!=-1){return find2;}return -1;}

相关文章:

33. 搜索旋转排序数组-二重二分查找

33. 搜索旋转排序数组-二分查找 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, n…...

mysql自动删除过期的binlog

一、binlog_expire_logs_seconds 配置项 mysql 8.0使用配置项 binlog_expire_logs_seconds 设置binlog过期时间&#xff0c;单位为秒。 mysql旧版本使用配置项 expire_logs_days 设置binlog过期时间&#xff0c;单位为天&#xff0c;不方便测试。 在 8.0 使用 expire_logs_d…...

Java面向对象(1)

static静态变量 public class Student {static String name;private double score;public Student(){};public Student(double score) {this.score score;}public double getScore() {return score;}public void setScore(double score) {this.score score;} }public class t…...

【计算机毕业设计】基于SpringBoot+Vue金融产品销售系统的设计与实现

博主主页&#xff1a;一季春秋博主简介&#xff1a;专注Java技术领域和毕业设计项目实战、Java、微信小程序、安卓等技术开发&#xff0c;远程调试部署、代码讲解、文档指导、ppt制作等技术指导。主要内容&#xff1a;毕业设计(Java项目、小程序、安卓等)、简历模板、学习资料、…...

【面试题精讲】Mysql如何实现乐观锁

❝ 有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top ❞ 首发博客地址 文章更新计划 系列文章地址 在 MySQL 中&#xff0c;可以通过使用乐观锁来实现并发控制&#xff0c;以避免数据冲突和并发更新问…...

从零开始搭建java web springboot Eclipse MyBatis jsp mysql开发环境

文章目录 1 第一步软件安装1.1 下载并安装Eclipse1.2 下载并安装Java1.3 下载并安装Apache Maven1.4 下载并安装MySQL 2 创建所需要的表和数据3 创建Maven 工程、修改jdk4 通过pom.xml获取所需要的jar包5 安装Eclipse的MyBatis插件6 创建文件夹以及jsp文件7 创建下面各种java类…...

【VsCode】整理代码

在VsCode中&#xff0c;你可以使用插件"Beautify"来格式化你的HTML代码&#xff0c;使其更加整齐清晰。而对于JSON代码&#xff0c;你可以使用"vscode-json"插件来格式化为易读的树状结构&#xff0c;方便查看和编辑。这些插件可以帮助你更加高效地整理HTM…...

盘点总结汇总植物病虫害、人体疾病识别相关的项目实践

在前面的很多项目中做了许多有关于植物病虫害比如&#xff1a;苹果病虫害、番茄病虫害、小麦病虫害、辣椒病虫害、白菜病虫害、木薯病虫害、葡萄病虫害、柑橘病虫害等等&#xff0c;还有一些是有关于人体疾病识别相关的&#xff0c;比如&#xff1a;病理细胞识别、癌症识别、皮…...

【测试开发】用例篇 · 熟悉黑盒测试用例设计方法(2)· 正交表 · 场景设计 · 常见案例练习

【测试开发】用例篇&#xff08;2&#xff09; 文章目录 【测试开发】用例篇&#xff08;2&#xff09;1. 正交表法1.1 什么是正交表1.2 两个重要概念1.3 如何通过正交表设计测试用例1.3.1 充分理解需求1.3.2 确定因素、确定水平1.3.3 allpairs画正交表1.3.4 补充正交表1.3.5 将…...

【ES】笔记-数值扩展

数值扩展 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>数值扩展</title> </head> &l…...

浅谈Rust内存管理

Rust因在内存管理上的独到之处&#xff0c;近年来受到了不少开发者的青睐。Rust内存管理的核心功能就是所有权。不同的语言采取了不同的内存管理方式&#xff0c;主要分为开发者手动管理或者编译器辅助管理&#xff0c;以及垃圾回收机制等。Rust的所有权机制&#xff0c;有别于…...

Vue路由跳转至页面后多次渲染

在 Vue 中&#xff0c;当你跳转到一个新的路由或者重新加载当前路由时&#xff0c;由于 Vue Router 或其他路由管理工具的机制&#xff0c;会导致该页面组件重新渲染多次的情况发生。这可能是因为以下原因&#xff1a; 组件复用&#xff1a;Vue Router 默认情况下会尝试复用已经…...

CDH大数据平台集群部署

文章目录 1. 资源准备2. 部署 Mariadb 数据库3. 安装CM服务4. 安装数据节点5. 登录CM系统 1. 资源准备 准备好CDH安装包资源&#xff0c;官方网站下载需要账号&#xff0c;如果没有账号可以去网上到处搜搜。主要涉及到的资源有&#xff1a; cloudera-manager-servercloudera-m…...

基于springboot+vue的校园资产管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...

@RequestMapping 注解使用技巧

一、RequestMapping 基础用法 用于将任意HTTP 请求映射到控制器方法上。 RequestMapping表示共享映射&#xff0c;如果没有指定请求方式&#xff0c;将接收GET、POST、HEAD、OPTIONS、PUT、PATCH、DELETE、TRACE、CONNECT所有的HTTP请求方式。GetMapping、PostMapping、PutMapp…...

AtCoder 265G 线段树

题意 传送门 AtCoder 265G 012 Inversion 题解 直接维护逆序对数量比较困难&#xff0c;考虑到元素值域很小&#xff0c;直接将不同数值对解耦进行维护。具体而言&#xff0c;线段树维护区间 0 , 1 , 2 0,1,2 0,1,2 的数量&#xff0c;以及满足 i < j i<j i<j 时…...

通俗易懂了解大语言模型LLM发展历程

1.大语言模型研究路程 NLP的发展阶段大致可以分为以下几个阶段&#xff1a; 词向量词嵌入embedding句向量和全文向量理解上下文超大模型与模型统一 1.1词向量 将自然语言的词使用向量表示&#xff0c;一般构造词语字典&#xff0c;然后使用one-hot表示。   例如2个单词&…...

Vim - 快速插入C语言函数注释模板

背景 C语言使用vim编写时&#xff0c;需要快速对函数进行说明头插入&#xff1b; 代码 function! InsertCFunctionHeader()" 获取当前行内容let line getline(.)" 匹配 C 函数定义let matched matchlist(line, ^\s*\w\ \\(\w\\)(\(.*\)))" 如果当前行不是函…...

Leetcode171. Excel 表列序号

给你一个字符串 columnTitle &#xff0c;表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。 例如&#xff1a; A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 题解&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱…...

自主设计,模拟实现 RabbitMQ - 实现 拒绝/否定 应答机制

目录 一、拒绝/否定 应答机制 1.1、需求分析 什么是 拒绝/否定 应答呢?...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...