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 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, n…...
mysql自动删除过期的binlog
一、binlog_expire_logs_seconds 配置项 mysql 8.0使用配置项 binlog_expire_logs_seconds 设置binlog过期时间,单位为秒。 mysql旧版本使用配置项 expire_logs_days 设置binlog过期时间,单位为天,不方便测试。 在 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金融产品销售系统的设计与实现
博主主页:一季春秋博主简介:专注Java技术领域和毕业设计项目实战、Java、微信小程序、安卓等技术开发,远程调试部署、代码讲解、文档指导、ppt制作等技术指导。主要内容:毕业设计(Java项目、小程序、安卓等)、简历模板、学习资料、…...
【面试题精讲】Mysql如何实现乐观锁
❝ 有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准https://blog.zysicyj.top ❞ 首发博客地址 文章更新计划 系列文章地址 在 MySQL 中,可以通过使用乐观锁来实现并发控制,以避免数据冲突和并发更新问…...
从零开始搭建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中,你可以使用插件"Beautify"来格式化你的HTML代码,使其更加整齐清晰。而对于JSON代码,你可以使用"vscode-json"插件来格式化为易读的树状结构,方便查看和编辑。这些插件可以帮助你更加高效地整理HTM…...
盘点总结汇总植物病虫害、人体疾病识别相关的项目实践
在前面的很多项目中做了许多有关于植物病虫害比如:苹果病虫害、番茄病虫害、小麦病虫害、辣椒病虫害、白菜病虫害、木薯病虫害、葡萄病虫害、柑橘病虫害等等,还有一些是有关于人体疾病识别相关的,比如:病理细胞识别、癌症识别、皮…...
【测试开发】用例篇 · 熟悉黑盒测试用例设计方法(2)· 正交表 · 场景设计 · 常见案例练习
【测试开发】用例篇(2) 文章目录 【测试开发】用例篇(2)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因在内存管理上的独到之处,近年来受到了不少开发者的青睐。Rust内存管理的核心功能就是所有权。不同的语言采取了不同的内存管理方式,主要分为开发者手动管理或者编译器辅助管理,以及垃圾回收机制等。Rust的所有权机制,有别于…...
Vue路由跳转至页面后多次渲染
在 Vue 中,当你跳转到一个新的路由或者重新加载当前路由时,由于 Vue Router 或其他路由管理工具的机制,会导致该页面组件重新渲染多次的情况发生。这可能是因为以下原因: 组件复用:Vue Router 默认情况下会尝试复用已经…...
CDH大数据平台集群部署
文章目录 1. 资源准备2. 部署 Mariadb 数据库3. 安装CM服务4. 安装数据节点5. 登录CM系统 1. 资源准备 准备好CDH安装包资源,官方网站下载需要账号,如果没有账号可以去网上到处搜搜。主要涉及到的资源有: cloudera-manager-servercloudera-m…...
基于springboot+vue的校园资产管理系统
博主主页:猫头鹰源码 博主简介:Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容:毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...
@RequestMapping 注解使用技巧
一、RequestMapping 基础用法 用于将任意HTTP 请求映射到控制器方法上。 RequestMapping表示共享映射,如果没有指定请求方式,将接收GET、POST、HEAD、OPTIONS、PUT、PATCH、DELETE、TRACE、CONNECT所有的HTTP请求方式。GetMapping、PostMapping、PutMapp…...
AtCoder 265G 线段树
题意 传送门 AtCoder 265G 012 Inversion 题解 直接维护逆序对数量比较困难,考虑到元素值域很小,直接将不同数值对解耦进行维护。具体而言,线段树维护区间 0 , 1 , 2 0,1,2 0,1,2 的数量,以及满足 i < j i<j i<j 时…...
通俗易懂了解大语言模型LLM发展历程
1.大语言模型研究路程 NLP的发展阶段大致可以分为以下几个阶段: 词向量词嵌入embedding句向量和全文向量理解上下文超大模型与模型统一 1.1词向量 将自然语言的词使用向量表示,一般构造词语字典,然后使用one-hot表示。 例如2个单词&…...
Vim - 快速插入C语言函数注释模板
背景 C语言使用vim编写时,需要快速对函数进行说明头插入; 代码 function! InsertCFunctionHeader()" 获取当前行内容let line getline(.)" 匹配 C 函数定义let matched matchlist(line, ^\s*\w\ \\(\w\\)(\(.*\)))" 如果当前行不是函…...
Leetcode171. Excel 表列序号
给你一个字符串 columnTitle ,表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 题解:力扣(LeetCode)官网 - 全球极客挚爱…...
自主设计,模拟实现 RabbitMQ - 实现 拒绝/否定 应答机制
目录 一、拒绝/否定 应答机制 1.1、需求分析 什么是 拒绝/否定 应答呢?...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
