Leetcode33搜索旋转排序数组

今天药忘吃喽~ 2022-10-02 00:43 160阅读 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

首先读题，一脸蒙蔽，后来发现没有一个特别好的方法能在时间复杂度O（logn）时间内解决，后来一看解析是剑指Offer一个思想很接近的题，当时就不是特别理解，现在通过实际编码来加深对它的印象。

题意本就是有序递增，只不过在某个地方进行了旋转，原题是寻找到最小数字，也是通过二分查找，只不过在二分查找过程中，需要对条件进行判断转移。即首先判断是否相等，不等再判断当前mid处于前面递增还是后面递增序列，再来决定。

不过原剑指offer上，并不要求必须递增不重复，即可能存在 111101这样的情况，需要额外判断。

附带33代码：

class Solution {
    public:
        int search(vector<int>& nums, int target) {
            
            if(nums.size()==0)
                return -1;
            
            int l = 0;
            int r = nums.size()-1;
            
            while(l<=r)
            {
                
                int mid = (l+r)/2;
                if(nums[mid]==target){
                    
                    return mid;
                }
                
                if(nums[mid]>=nums[r]){
                //mid在前面递增数组
                  if(target>nums[mid]){
                      l = mid+1;
                  }else if(target>nums[r]){
                      r = mid-1;
                  }else{
                      l = mid+1;
                  }  
                    
                }else{
                 //mid在 后面的数组   
                    if(target<nums[mid]){
                        r = mid-1;
                    }else if(target>nums[r]){
                        r = mid-1;
                    }else{
                        l = mid+1;
                    }
                    
                }
                
                
            }
            
            
            
            return -1;
            
        }
    };