33. Search in Rotated Sorted Array

Leetcode Array Binary Search

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

分析

这道题是二分查找Search Insert Position的变体，看似有点麻烦，其实理清一下还是比较简单的。因为rotate的缘故，当我们切取一半的时候可能会出现误区，所以我们要做进一步的判断。具体来说，假设数组是A，每次左边缘为$lo$，右边缘为$hi$，还有中间位置是$mid$。在每次迭代中，分三种情况：

1. 如果target==A[mid]，那么m就是我们要的结果，直接返回；
2. 如果A[mid]<A[hi]，那么说明从$mid$到$hi$一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在$mid$到$hi$之间，如果是则把左边缘移到$mid+1$，否则就target在另一半，即把右边缘移到$mid-1$。 （3）如果A[mid]>=A[hi]，那么说明从$lo$到$mid$一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。

根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是$O(\log n)$，空间复杂度是$O(1)$。

递归版本：

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    return search(nums, 0, nums.length - 1, target);
}

private int search(int[] nums, int lo, int hi, int target) {
    int mid = (lo + hi) / 2, midVal = nums[mid];
    if (midVal == target) return mid;
    if (lo >= hi) return -1;
    if (midVal >= nums[lo]) {
        if (midVal > target &&  target >= nums[lo]) return search(nums, lo, mid - 1, target);
        else return search(nums, mid + 1, end, target);
    } else {
        if (midVal < target && target <= nums[hi]) return search(nums, mid + 1, hi, target);
        else return search(nums, lo, mid - 1, target);
    }
}

迭代版本：

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int lo = 0, hi = nums.length - 1, mid, midVal;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        midVal = nums[mid];
        if (midVal == target) return mid;
        if (midVal >= nums[lo]) {
            if (midVal > target &&  target >= nums[lo]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (midVal < target && target <= nums[hi]) lo =  mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Python

def search(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """

    left = 0
    right = len(nums)  - 1
    found = False

    while left <= right and not found:
        mid = (left + right ) // 2
        print left, right, mid


        if nums[mid] == target:
            found = True
            return mid

        elif nums[left] <= nums[mid]:
            if  target >= nums[left] and target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        else:
            if  target >= nums[mid] and target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1