leetcode力扣33.搜索旋转排序数组

电玩女神 2023-03-01 12:22 132阅读 0赞

**题目：**

> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
> 
> ( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。  
>   
> 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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

**分析：**

如果是二分查找的话，那么很容易；但是这个数组旋转过了，不过题目已经严格要求了时间复杂度，显然还是要用二分的。

之前有一个题目：153题，搜索旋转排序数组的最小值，同样的题干，但是只求旋转点，就是说求最小值的位置。链接在这里：

*  所以第一个思路就是，**先找到旋转点**，然后就可以决定在旋转的两遍的哪一边进行二分查找target；
 *  另一个思路就是正常的二分，但是缩小范围的过程要多加**额外的处理**。

### 一、一次二分 ###

![在这里插入图片描述][20200725104607689.png]

每一次mid，和target的大小关系当然还是三种，没有区别。  
但是**大于小于的情况又需要细分**：

1.  > target：
    
    1.  可能是在这个旋转数组的左边上升区间，
    2.  也可能是在这个旋转数组的右边上升区间；
2.  < target：
    
    1.  同样可能是在这个旋转数组的左边上升区间，
    2.  也可能是在这个旋转数组的右边上升区间。

class Solution {
        
        public int search(int[] nums, int target) {
        
            if( nums.length<1 )return -1;
            int i = 0;
            int j = nums.length-1;
            //查找旋转位置
            while( i <= j ){
        
                int mid = i + (j-i)/2;
                if( nums[mid] == target ){
        
                    return mid;
                }
                if( nums[mid] >= nums[i] ){
        
                    //mid在左边的位置
                    if( nums[mid] > target && target >= nums[i] ){
        
                        j = mid-1;
                    }else{
        
                        i = mid+1;
                    }
                }else{
        
                    //mid在右边的位置
                    if( nums[j] >= target && target > nums[mid] ){
        
                        i = mid+1;
                    }else{
        
                        j = mid-1;
                    }
                }
            }
            return -1;
        }
    }

这个方法一次二分，但是个人认为比较绕。

### 二、两次二分 ###

借助模板2，`先用一次二分找到最小值`，也就是数组旋转的位置，然后进行`第二次二分`，这时候采用的就是普通的模板1。

class Solution {
        
        public int search(int[] nums, int target) {
        
            if( nums.length<1 )return -1;
            int i = 0;
            int j = nums.length-1;
            int pos = 0;
            //查找旋转位置
            while( i < j ){
        
                int mid = i + (j-i)/2;
                if( nums[mid] > nums[j] ){
        
                    i = mid+1;
                }else{
         j = mid; }
            }
            pos = i;
    
            if( target > nums[nums.length-1] ){
        
                i = 0;j = pos-1;
            }else{
        
                i = pos;j = nums.length-1;
            }
            //二分
            pos = -1;
            while( i <= j ){
        
                int mid = i + (j-i)/2;
                if( nums[mid]<target ){
        
                    i = mid+1;
                }else if( nums[mid]>target ){
        
                    j = mid-1;
                }else{
        
                    pos = mid;break;
                }
            }
            return pos;
        }
    }

这种写法似乎更清晰一些。

[20200725104607689.png]: /images/20230208/4d146885ccbb4b81b99cddcf97794bae.png