首页 > 其他分享 >33. Search in Rotated Sorted Array[Medium]

33. Search in Rotated Sorted Array[Medium]

时间:2023-01-29 18:56:11浏览次数:48  
标签:Search Medium target nums 33 mid int right left

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Constraints:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -10^4 <= target <= 10^4

Example

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

思路

二分查找变体,在二分查找基础上,再多一步条件判断,看当前处于哪一段

题解

    public int search(int[] nums, int target) {
        int left, right, mid;
        left = 0;
        right = nums.length - 1;

        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target)
                return mid;
            // 如果满足,说明左半段是顺序的
            if (nums[mid] >= nums[left]) {
                // 那如果比最左小或者比中位大,那只可能在右半段了
                if (target < nums[left] || target > nums[mid])
                    left = mid + 1;
                else
                    right = mid - 1;
            } else {
                // 说明右半段是顺序的,刨除右半部分(比最右大或比中位小),那就是左半段
                if (target > nums[right] || target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }

        }
        return -1;
    }

标签:Search,Medium,target,nums,33,mid,int,right,left
From: https://www.cnblogs.com/tanhaoo/p/17073599.html

相关文章

  • *153. Find Minimum in Rotated Sorted Array[Medium]
    153.FindMinimuminRotatedSortedArraySupposeanarrayoflengthnsortedinascendingorderisrotatedbetween1andntimes.Forexample,thearraynums......
  • CF1033E 题解
    题意传送门交互题,给定一个简单连通图,你可以询问一个点集\(s\),返回其导出子图的边数。判断此图是否为二分图:若是,输出其中一部点的集合;否则输出任一个奇环。最多询问\(20......
  • ElasticSearch+Kibana+Filebeat+Head搭建日志采集系统
    安装步骤如下:1.进入elasticsearch官网下载:​​​https://www.elastic.co/downloads/elasticsearch​​​cd/usr/local/wget​​https://artifacts.elastic.co/download......
  • Elasticsearch的性能优化
     Elasticsearch的默认配置项是比较全面的,在不做太多配置的情况下可以使用es的全文检索,高亮显示,聚合,和数据的索引。但是在比较了解es的情况下,可以对很对配置进行优化。一、......
  • elasticsearch 初学笔记
    目录安装使用createindexlistindexcreateanewdocumentgetdocumentgetdocumentbyidlistalldocumentsofindex模糊查询正则查询参考如果觉得有用,希望能在github......
  • 谷粒商城--整合Elasticsearch和商品的上架
    整合Elasticsearch和商品的上架​​一、整合ES​​​​ES常用概念​​​​索引,类型,文档是什么?​​​​倒排索引​​​​相关度分数score的计算​​​​安装ES和Kibana​​​......
  • (20)go-micro微服务Elasticsearch使用
    目录一Elasticsearch介绍二Elasticsearch的主要功能及应用场景1.Elasticsearch主要具有如下功能:2.Elasticsearch的主要应用场景如下:三Elasticsearch核心概念四Elasti......
  • Elasticsearch 核心技术与实战 学习笔记
    分片的设定对于生产环境中分片的设定,需要提前做好容量规划分片数设置过小导致后续无法增加节点实现水品扩展单个分片的数据量太大,导致数据重新分配耗时分片数设......
  • python桌面应用自动化,uiautomation模块的Depth和searchDepth心得
    最近在学习yinkaisheng大神写的uiautomation模块,Depth和searchDepth一直使用不好,明明Depth=3,居然可以用searchDepth=1找到,网上也没找到答案,就自己试验了多次,终于发现了问题......
  • Android 13(API 33)读写SD卡权限的调整适配
    在Android13前读取SDcard的内容只需要一个权限:android.permission.READ_EXTERNAL_STORAGE 但是在Android13以后这个权限被细化成了三个:publicstaticfi......