卖萌的弱渣

I am stupid, I am hungry.

Search in Rotated Sorted Array

Search in Rotated Sorted Array

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.

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Solution

  • Time: O(log n)
  • 若target == A[mid]，索引找到，直接返回
  • 寻找局部有序数组，分析A[mid]和两段有序的数组特点，由于旋转后前面有序数组最小值都比后面有序数组最大值大。故若A[start] < A[mid]成立，则start与mid间的元素必有序（要么是前一段有序数组，要么是后一段有序数组，还有可能是未旋转数组）。
  • 接着在有序数组A[start]~A[mid]间进行二分搜索，但能在A[start]~A[mid]间搜索的前提是A[start] <= target <= A[mid]。
  • 接着在有序数组A[mid]~A[end]间进行二分搜索，注意前提条件。
(Search-In-Rotated-Sorted-Array.py) download
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
28
29
30
31
32
33
34
35

class Solution:
    """
    @param A : a list of integers
    @param target : an integer to be searched
    @return : an integer
    """
    def search(self, A, target):
        # write your code here
        if not A:
            return -1
        front = 0
        end = len(A) - 1

        while front<=end:
            mid = front + (end-front)/2
            if A[mid] == target:
                return mid
            # Case 1: [A[front], A[mid]] is sorted
            if A[front] < A[mid]:
                # A[mid] > target, then target could be in another subarray or [A[front], A[mid]]
                if A[mid] > target and A[front] <= target:
                    end = mid-1
                # A[mid] too large
                else:
                    front = mid+1
            else:
            # Case 2: [A[front],A[end]] is sorted
                    # any values of left subarray are larger than right subarray 
                    # A[mid] < target, value could be in [A[mid] ...] or [A[front] ... pivot]
                    # Go left
                    if A[mid] < target and A[end] >= target:
                        front = mid+1
                    else:
                        end = mid-1
        return -1