Leetcode 33. 搜索旋转排序数组

た入场券 2022-09-07 01:22 207阅读 0赞

#### 题目重述 ####

整数数组 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 。

##### 示例 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

##### 提示： #####

1 <= nums.length <= 5000
    -10^4 <= nums[i] <= 10^4
    nums 中的每个值都 独一无二
    题目数据保证 nums 在预先未知的某个下标上进行了旋转
    -10^4 <= target <= 10^4

进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

*  看到有序+O(logn)，应该想到二分
 *  将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的
 *  如果左右中某部分是有序的，并且target还在该范围，那么就按照二分查找来就行的，而如果target不在有序的那部分，那么就锁定范围为非有序的那部分，处理就行

#### Java实现 ####

class Solution {
        
        public int search(int[] nums, int target) {
        
            int left = 0,right = nums.length - 1,mid ;
    
            while (left <= right){
        
                mid = (left + right)/2;
                if(nums[mid] == target){
        
                    return mid;
                }
                // 左局部有序
                if(nums[left] <= nums[mid]){
        
                    // 如果target在该范围，缩小范围,因为之前判断过target不等于num[mid],故不用加等号(target <nums[mid])
                    if(nums[left] <= target && target <nums[mid]){
        
                        right = mid - 1;
                    }else{
        
                        left = mid + 1;
                    }
                }else {
        // 右局部有序
                    // 如果target在该范围，缩小范围
                    if(nums[mid] < target && target <=nums[right]){
        
                        left = mid + 1;
                    }else{
        
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }
    }