Search in Rotated Sorted Array

标签： C++ 算法 LeetCode 数组 困难 二分法

每日算法——leetcode系列

问题 Search in Rotated Sorted Array

Difficulty: Hard

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

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

翻译

在旋转排序数组中搜索(指定的目标)

难度系数：困难
假定一个有序数组在一个预先不知道的轴点地方被旋转。
例如，0 1 2 4 5 6 7可能会变为4 5 6 7 0 1 2。
给你一个目标值去搜索，如果在数组中找到了则返回它的索引，否则返回-1。
你可以假定数组中没有重复的元素。

思路

对于有序数组， 查找可以用二分查找，但由于是事先不知道在什么地方旋转过的，一开始想法简单粗暴， 找出旋转的轴点位置， 再把他旋转回有序状态， 再二分查找，最后再用旋转后跟旋转前的索引对应关系找到index。这个时间复杂度有点高。

直接分析旋转后的数组：
假定start, end, mid分别代表起始、末尾、中间索引
二分法思想：

• 如果 nums[mid] == target, 找到， 如果没找到则确定target所在的索引范围
• 如果 nums[start] <= num[mid]

1. 可以证明start到mid是有序的且不存在满足nums[start] <= x <= num[mid]的x在start和mid的外边（反证法）
   如果是target也满足nums[start] <= target <= num[mid]， 那么target的索引在start和mid间
2. 同理可以证明如果target不满足上面的不等式， 那么target的索引在mid+1和end之间

• 如果 nums[start] > num[mid]

1. 可以证明mid+1到end是有序的且不存在满足nums[mid+1] <= x <= num[end]的x在mid和end的外边（反证法）
   如果是target也满足nums[mid+1] <= target <= num[end]， 那么target的索引在mid+1和end之间
2. 同理可以证明如果target不满足上面的不等式， 那么target的索引在start和mid之间

代码

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