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

leetcode33.搜索旋转排序数组

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

在传递给函数之前,nums 在预先未知的某个下标 k0 <= 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

思路:直接先按照正常情况写代码 然后考虑异常情况;详情见下面代码:

public int search(int[] nums, int target) {int low=0;int high=nums.length-1;int mid=low+(high-low)/2;while(low<=high){if(nums[mid]==target)return mid;else if(nums[mid]<target){// 异常情况:右边区间是有序的且右边最大值也<targetif(nums[mid]<=nums[high]&&nums[high]<target)high=mid-1;// 正常应该到右边区间找elselow=mid+1;}else if(nums[mid]>target){//异常情况:左边区间有序且最小值也>targetif(nums[mid]>=nums[low]&&nums[low]>target)low=mid+1;// 正常情况应该到左边区间找elsehigh=mid-1;}mid=low+(high-low)/2;}return -1;}

http://www.lryc.cn/news/501570.html

相关文章:

  • Ansible自动化运维(三)playbook剧本详解
  • 通过PS和Unity制作2D动画之二:IK的使用
  • 图像边缘检测原理和常用检测算子及MATLAB实现
  • 企业经营数据分析系统:提升决策能力的利器
  • 【49】AndroidStudio构建其他人开发的Android项目
  • Oracle 数据库中SERIALLY_REUSABLE包是一种特殊的包类型
  • css基础记录
  • Python后端 -- 万字长文全面解析Django框架
  • el-thee懒加载删除某条数据 ,el-thee懒加载重置,el-thee刷新某个节点
  • 【PyQt5教程 四】Qt Designer 样式表(styleSheet)实现基本小部件的自定义动态效果和资源浏览器背景添加方法
  • 【git】--- 通过 git 和 gitolite 管理单仓库的 SDK
  • 计算机网络之NAT、代理服务、内网穿透、内网打洞
  • 2024-金盾信安杯线上赛 WP
  • MySQL 基础架构
  • 汽车升级到底应不应该设置“可取消“功能
  • 【MySQL】mysql中的事务
  • 大语言模型(LLM)与智能机器人的应用分析
  • Inno Setup 学习笔记(一)
  • 从阿里云EDM到美团云:典型微服务治理平台的实战经验分享
  • 【接口自动化测试】一文从3000字从0到1详解接口测试用例设计
  • 反向代理-缓存篇
  • 【伪代码】数据结构-期末复习 线性表
  • JavaWeb学习、过滤器、ajax异步请求、json、jquery-api文档
  • 深入探索 JVM:原理、机制与实战
  • JavaWeb学习(3)(Servlet详细、Servlet的三种实现方式(面试)、Servlet的生命周期、传统web.xml配置Servlet(了解))
  • 支付宝租赁小程序助力便捷生活新方式
  • Linux-ubuntu环境配置
  • 深入解析下oracle的number底层存储格式
  • nginx代理rabbitmq和配置 Nginx 代理达梦数据库
  • 汉语唤醒词的模糊判断(Python)