Leetcode(33) Search in Rotated Sorted Array

发表于 | 分类于

Description

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:

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

Example 2:

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

解法

查找的题，又要求时间复杂度为O(logn)，显然是要采用二分的算法，二分可以一次将查找范围缩小一半。而二分的前提应该是查找数组为有序的，观察一下这道题的数组情况。

对于数组[0 1 2 4 5 6 7] 共有下列七种旋转方法：

0　　1　　2　　 4　　5　　6　　7

7　　0　　1　　 2　　4　　5　　6

6　　7　　0　　 1　　2　　4　　5

5　　6　　7　　 0　　1　　2　　4

4　　5　　6　　7　　0　　1　　2

2　　4　　5　　6　　7　　0　　1

1　　2　　4　　5　　6　　7　　0

可以发现，无论如何旋转，至少有一半的序列都是有序的，仔细想想，也很有道理。所以，可以随意选取当前查找范围的一半，如果当前无序，则另一半必有序。以右区间为例，有序的判断条件为nums[mid] <= nums[right]。每次只处理有序区间，判断当前元素是否位于该有序区间之中，是，则将区间缩小为有序区间，否，则将区间缩小为无序区间，无序区间下一次循环再判断其左右子区间有序状态做进一步地缩小。这样，每次缩小的范围为当前区间的一半。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] <= nums[right]) {
                if (target >= nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (target >= nums[left] && target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}