[数据结构与算法]leetcode--搜索旋转排序数组

题目

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

**进阶：**你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

思路

旋转数组有一个特点：将数组从任意地方切成两半，至少有一半是单调递增的。

让我们看一个例子[0,1,2,4,5,6,7]在下标 3 处旋转，得到 nums = [4,5,6,7,0,1,2]。

• 若 mid = 3，则nums[0]->nums[mid]是单调递增的。nums[mid + 1]到最后也是单调递增的

• 其他情况，要么左半部分是递增的，要么右半部分是递增的。

对于递增部分，我们可以使用二分法，那么我们能不能每次只处理递增部分呢？答案是肯定的。具体搜索过程为

• 若 nums[mid] == target直接返回答案

• 若左半部分是递增的，即nums[l] <= nums[mid]（这时，左半部分肯定是递增的，由上图就可以看出），我们判断target是否落在该区间中，即nums[l] <= target < nums[mid]

  • 若在，令r = mid - 1，然后在该区间内搜索
  • 若不在，则令l = mid + 1，转到右半边去搜索，因为答案不可能在左半边出现了

• 若右半部分是递增的，即nums[r] >= nums[mid]（这时，右半部分肯定是递增的，由上图就可以看出），我们判断target是否落在该区间中，即nums[mid] < target <= nums[mid]

  • 若在，令l = mid + 1，然后在该区间内搜索
  • 若不在，则令r = mid - 1，转到左半边去搜索，因为答案不可能在右半边出现了

这样，我们每次处理的都是递增区间，每次都缩小一半的搜索范围，能够快速找到结果。

代码

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) - 1;
       int l = 0 , r = n - 1;
       while(l <= r){
           int mid = (l + r) / 2;
           if(nums[mid] == target) return mid;
           if(nums[l] <= nums[mid]){ // l 和 mid 都在单调递增序列中
               if(nums[l] <= target && nums[mid] > target)
                   r = mid - 1; // 若在该区间中,直接将搜索范围锁定到该区间
                else l = mid + 1; // 否则,在搜索范围中排除该区间
           }
           else{ // mid 和 r 都在单调递增序列中
               if(nums[mid] < target && nums[r] >= target)
                    l = mid + 1; // 若在该区间中,直接将搜索范围锁定到该区间
                else r = mid - 1; // 否则,在搜索范围中排除该区间
           }
       }
       return -1;
    }
};