LeetCode 33. Search in Rotated Sorted Array

[Woodyiiiiiii]

Suppose an array sorted in ascending order 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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

---

首先理清下思路，题目要求时间复杂度为O(log n)，那么最容易想到的就是二分查找了。二分查找法是针对排序好的数组，找到中间值，如果它小于目标值，则在右半边继续查找，否则在左半边。而这道题的情景是一个有序数组旋转而成，数组无序，所以我们无法确定继续往左半边查找还是往右半边查找，那么关键是如何判断左半边还是右半边有序呢，如何改进二分查找呢？

我们没有思路的话，就尝试着举几个例子找规律(找链表中间节点也是举例子得出的规律)。比如数组[0, 1, 2, ..., 7]，会有7种旋转后的情况。我们配合二分查找的步骤观察，可以发现一个规律：若中间值小于最右边的数值，那么数组右半边排好序；反之数组左半边排好序。然后我们根据目标数值和中间数值的比对，可以选择保留哪一边，继续二分查找。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
}

对于以上解法，有个小问题：为什么是中间值跟最右边的值对比？而不是最左边呢？最左边数值对比一样满足以上规律啊？

在二分搜索中，nums[mid] 和 nums[left] 还有可能相等的，
当数组中只有两个数字的时候，比如 [3, 1]，那该去取那一边呢？
由于只有两个数字且 nums[mid] 不等于 target，target 只有可能在右半边出现。
最好的方法就是让其无法进入左半段，就需要左半段是有序的，
而且由于一定无法同时满足 nums[left] <= target && nums[mid] > target，
因为 nums[left] 和 nums[mid] 相等，
同一个数怎么可能同时大于等于 target，又小于 target。
由于这个条件不满足，则直接进入右半段继续搜索即可，
所以等于的情况要加到 nums[mid] > nums[left] 的情况中，变成大于等于。
参见代码如下：

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

---

参考资料:

1. LeetCode原题
2. [LeetCode] 33. Search in Rotated Sorted Array grandyang/leetcode#33