leetcode：33. 搜索旋转排序数组

题目来源

题目描述

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    

    }
};

题目解析

思路

• 因为是有序数组，所以我们应该去二分
• 但是这里是一个原本有序的数组在某个点上进行了旋转，也就会将一段原本升序的数组分成了两段
• 可以先使用二分法找到旋转点，再使用二分法在两个数组中分别寻找target。

class Solution {
    
    int find(vector<int>& nums, int l, int r, int target){
    
        while (l <= r){
    
            int mid = l + (r - l) / 2;
            if(nums[mid] == target){
    
                return mid;
            }else if(nums[mid] < target){
    
                l = mid + 1;
            }else{
    
                r = mid - 1;
            }
        }
        return -1;
    }
public:
    int search(vector<int>& nums, int target) {
    
        int n = nums.size();
        int idx = 0;
        for (int i = 0; i < n - 1; ++i) {
    
            if(nums[i] > nums[i + 1]){
    
                idx = i;
                break;
            }
        }
        
        int ans = find(nums, 0, idx, target);
        if(ans != -1 && idx + 1 < n){
    
            ans = find(nums, idx + 1, n - 1, target);
        }
        return ans;
    }
};

二分解法

二分的本质是两段性，只要某一段满足某个性质，另一段不满足某个性质，就可以用[二分]

经过旋转的数组，显然前半段满足>= nums[0]，而后半段不满足 >= nums[0]。我们可以以此作为依据，通过「二分」找到旋转点。

找到旋转点之后，再通过比较 target 和 nums[0] 的大小，确定 target 落在旋转点的左边还是右边。

class Solution {
    

public:
    int search(vector<int>& nums, int target) {
    
        int n = nums.size();
        if(n == 0){
    
            return -1;
        }
        if(n == 1){
    
            return nums[0] == target ? 0 : -1;
        }

        // 第一次「二分」：从中间开始找，找到满足 >=nums[0] 的分割点（旋转点）
        int l = 0, r = n - 1;
        while (l < r){
    
            int mid = (l + r) / 2;
            if(nums[mid] >= nums[0]){
    
                l = mid;
            }else{
    
                r = mid - 1;
            }
        }

        // 第二次「二分」：通过和 nums[0] 进行比较，得知 target 是在旋转点的左边还是右边
        if(target >= nums[0]){
    
            l = 0;
        }else{
    
            l = l + 1;
            r = n - 1;
        }

        while(l < r){
    
            int mid = (l + r) >> 1;
            if(nums[mid] >= target){
    
                r = mid;
            }
            else l = mid + 1;
        }
        return (nums[r] == target ? r : -1);
    }
};

思路一

对于旋转数组，nums = [4,5,6,7,0,1,2]

• 首先根据nums[0]与target的关系判断target是在左段还是右段
  • 例如 target = 5, 目标值在左半段，因此在 [4, 5, 6, 7, inf, inf, inf] 这个有序数组里找就行了；
  • 例如 target = 1, 目标值在右半段，因此在 [-inf, -inf, -inf, -inf, 0, 1, 2] 这个有序数组里找就行了。
• 如此，我们又双叒叕将「旋转数组中找目标值」 转化成了 「有序数组中找目标值」

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    
        int lo = 0,  hi = nums.size() - 1l;
        while (lo <= hi){
    
            int mid  = lo + (hi - lo) / 2;
            if(nums[mid] == target){
    
                return mid;
            }

            // 先根据 nums[0] 与 target 的关系判断目标值是在左半段还是右半段
            if(target >= nums[0]){
    
                // 目标值在左半段时，若 mid 在右半段，则将 mid 索引的值改成 inf
                if (nums[mid] < nums[0]) {
    
                    nums[mid] = INT32_MAX;
                }
            }else{
    
                // 目标值在右半段时，若 mid 在左半段，则将 mid 索引的值改成 -inf
                // 目标值在右半段时，若 mid 在左半段，则将 mid 索引的值改成 -inf
                if (nums[mid] >= nums[0]) {
    
                    nums[mid] = INT32_MIN;
                }
            }
            
            if(nums[mid] < target){
    
                lo = mid + 1;
            }else{
    
                hi = mid - 1;
            }
        }
        return -1;
    }
};

思路二：

• 将数组一分为二，其中一个一定是有序的，另一个可能是有序的，也可能是部分有序的。此时有序部分用二分法查找。其中一个一定有序，另一个可能有序，可能无序。就这样循环.

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    
        int l = 0,  r = nums.size() - 1l;
        while (l <= r){
    
            int mid  = l + (r - l) / 2;
            if(nums[mid] == target){
    
                return mid;
            }
            
            
            if(nums[l] <= nums[mid]){
       //mid左侧为有序数组
                if(nums[l] <= target  && target < nums[mid]){
    //如果target在mid左侧的话
                    r = mid - 1; 
                }else{
    //在mid右侧
                    l = mid + 1;
                }
            }else{
      //mid右侧为有序数组
                if(nums[mid] < target && target <= nums[r]){
    //如果target在mid右侧的话
                    l = mid + 1;
                }else{
    //在mid左侧
                    l = mid - 1;
                }
                
                // 为什么只在target与nums[l]或nums[r]比较的时候取等，而不在其他位置取等？
                // 因为另一边的 nums[mid] == target 是否相等 已经在上面的 if 分支里判断了
            }
        }
        return -1;
    }
};