Wednesday, November 12, 2014

[LeetCode] Search in Rotated Sorted Array I, II

Search in Rotated Sorted Array I

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.

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.


思路:Search in Rotated Sorted Array I

题目一看就知道是binary search。所以关键点在于每次要能判断出target位于左半还是右半序列。解这题得先在纸上写几个rotated sorted array的例子出来找下规律。Rotated sorted array根据旋转得多少有两种情况:

原数组:0 1 2 4 5 6 7
情况1:  6 7 0 1 2 4 5    起始元素0在中间元素的左边
情况2:  2 4 5 6 7 0 1    起始元素0在中间元素的右边

两种情况都有半边是完全sorted的。根据这半边,当target != A[mid]时,可以分情况判断:

当A[mid] < A[end] < A[start]:情况1,右半序列A[mid+1 : end] sorted
A[mid] < target <= A[end], 右半序列,否则为左半序列。

当A[mid] > A[start] > A[end]:情况2,左半序列A[start : mid-1] sorted
A[start] <= target < A[mid], 左半序列,否则为右半序列

Base case:当start + 1 = end时
假设 2 4:
A[mid] = A[start] = 2 < A[end],A[mid] < target <= A[end] 右半序列,否则左半序列

假设 4 2:
A[mid] = A[start ] = 4 > A[end],  A[start] <= target < A[mid] 左半序列,否则右半序列

加入base case的情况,最终总结的规律是:

A[mid] =  target, 返回mid,否则

(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end]  右半,否则左半。

(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid] 左半,否则右半。

递归解法:

 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
class Solution {
public:
    int search(int A[], int n, int target) {
        return searchRotatedSortedArray(A, 0, n-1, target);
    }
    
    int searchRotatedSortedArray(int A[], int start, int end, int target) {
        if(start>end) return -1;
        int mid = start + (end-start)/2;
        if(A[mid]==target) return mid;
        
        if(A[mid]<A[end]) { // right half sorted
            if(target>A[mid] && target<=A[end])
                return searchRotatedSortedArray(A, mid+1, end, target);
            else
                return searchRotatedSortedArray(A, start, mid-1, target);
        }
        else {  // left half sorted
            if(target>=A[start] && target<A[mid]) 
                return searchRotatedSortedArray(A, start, mid-1, target);
            else
                return searchRotatedSortedArray(A, mid+1, end, target);
        }
    }
};


递归解法很容易改写成迭代解法:

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


思路:Search in Rotated Sorted Array II


当有重复数字,会存在A[mid] = A[end]的情况。此时右半序列A[mid-1 : end]可能是sorted,也可能并没有sorted,如下例子。

3 1 2 3 3 3 3
3 3 3 3 1 2 3

所以当A[mid] = A[end] != target时,无法排除一半的序列,而只能排除掉A[end]:

A[mid] = A[end] != target时:搜寻A[start : end-1]

正因为这个变化,在最坏情况下,算法的复杂度退化成了O(n):
序列 2 2 2 2 2 2 2 中寻找target = 1。

迭代解法:


 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:
    bool search(int A[], int n, int target) {
        int start = 0, end = n-1;
        while(start<=end) {
            int mid = start + (end-start)/2;
            if(A[mid]==target) return true;  
       
            if(A[mid]<A[end]) { // right half sorted
                if(target>A[mid] && target<=A[end])
                    start = mid+1;
                else
                    end = mid-1;
            }
            else if(A[mid]>A[end]) {  // left half sorted
                if(target>=A[start] && target<A[mid]) 
                    end = mid-1;
                else
                    start = mid+1;
            }
            else {
                end--;
            }
        }
        return false;
    }        
};

4 comments:

  1. A[mid] = target, 返回mid,否则

    (1) A[mid] < A[end]: A[mid+1 : end] sorted
    A[mid] < target <= A[end] 右半,否则左半。

    (2) A[mid] >= A[end] : A[start : mid-1] sorted
    A[start] <= target < A[mid] 左半,否则右半。

    ReplyDelete
  2. end-- 改成 end = m+1; 还是o(log n)

    ReplyDelete

  3. end-- 改成 end = mid+1; 还是o(log n)

    ReplyDelete