精选力扣500题第15题 LeetCode 33. 搜索旋转排序数组【c++详细题解】

骑猪看日落 2021-07-24 15:15 317阅读 0赞

### 1、题目 ###

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

### 2、思路 ###

**(二分)**  O ( l o g n ) O(logn) O(logn)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
1、先找到旋转点，在旋转点左边的点都比`nums[0]`大，右边的点都比`nums[0]`小，因此可以用二分找到该点

*  当`nums[n - 1] > nums[mid]`时，往左边区域找
 *  当`nums[n - 1] <= nums[mid]`时，往右边区域找  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1][]

2、找到旋转点l后，可以知道`[0,l - 1]`,`[l,n - 1]`是两个有序数组，判断出`target`的值在哪个有序数组中，确定好二分的区间`[l,r]`

3、在`[l,r]`区间中，由于该区域也具有单调性，通过二分找到该值的位置

*  当`nums[mid] >= target`时，往左边区域找
 *  当`nums[mid] < target`时，往右边区域找
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]

4、若最后找到的元素`nums[r] != target`，则表示不存在该数，返回`-1`，否则返回该数值

### 3、代码 ###

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

**原题链接：**[33. 搜索旋转排序数组][33.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/f682dbb770c344e2bfbf402144ede168.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/20c4aa631a83442a9ff887cc5ab89c33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/7dd75f6cb1ee4193b4e98da393ad4211.png
[33.]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/8bfc4e172dfd4f07ad6a0f82a39fd9a1.png