Leetcode 33. 搜索旋转排序数组

题目描述

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

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

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

解题思路

这道题一看按升序排列，就首先想到了二分法。但是其中有部分连续序列是经过旋转处理的，整体就不再是有序的了，那么我们还能使用二分法么？

答案是肯定的（不行也要创造条件上！）。这道题的一个难点就是得观察得出：**当整个序列从mid出分为两部分后，总有一部分是有序的。**据此，我们考虑使用二分法来解答这道题。

具体的过程如下：

  1. 如果左半部分有序
  • 如果target处于左半部分中，那么只需在左半部分中二分查找；
  • 如果target不在左半部分中，那么在后半部分查找即可；
  1. 如果后半部分有序
  • 如果target处于右半部分中，那么只需在右半部分中二分查找；
  • 如果target不在右半部分中，那么在左半部分查找即可。

根据思路，我们可以得出相应的代码。

示例代码

  1. 递归版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int research_run(vector<int>&nums,int target,int left,int right)
{
    int mid=(left+right)/2;
    if(target==nums[mid]) return mid;
    if(left==right&&nums[left]!=target) return -1;
    if(nums[left]<nums[mid])
    {
        if(nums[left]<=target&&target<=nums[mid])
        {
            return research_run(nums,target,left,mid-1);
        }
        else{
            return research_run(nums,target,mid+1,right);
        }
    }
    else{
        if(nums[mid]<=target&&target<=nums[right])
        {
            return research_run(nums,target,mid+1,right);
        }
        else{
            return research_run(nums,target,left,mid-1);
        }
    }
}

int search(vector<int>&nums,int target)
{
    return research_run(nums,target,0,nums.size()-1);
    
}

这个版本在本地IDE显示答案正确，但是提交显示超时。所以，对代码进行了进一步的简化：将能合并的逻辑判断进行了合并，得到了AC的递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int research_run(vector<int>&nums,int target,int left,int right)
{
    int mid=(left+right)/2;
    if(target==nums[mid]) return mid;
    if(left==right&&nums[left]!=target) return -1;
    if(nums[left]<nums[mid]&&nums[left]<=target&&target<=nums[mid])
    {
       return research_run(nums,target,left,mid-1);
    }
    else if(nums[left]>nums[mid]&&!(nums[mid]<=target&&target<=nums[right]))
    {
        return research_run(nums,target,left,mid-1);
    }
    else{
        return research_run(nums,target,mid+1,right);
    }
}

int search(vector<int>&nums,int target)
{
    return research_run(nums,target,0,nums.size()-1);
    
}
  1. 迭代版本

将递归版本改为迭代版本如下：

1
2
3
4
5
int search(vector<int>&nums,int target)
{
    return research_run(nums,target,0,nums.size()-1);
    
}