Search in Rotated Sorted Array

Date:

　　Oct 29, 2017

Problem:

　　https://leetcode.com/problems/search-in-rotated-sorted-array/description/

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.

　　描述中的rotate有误导人的嫌疑，题意其实是要求将一个升序数列截成两段调换位置，然后从数列中查找一个给定的target，若找到，返回其位置，否则返回-1。

　　直观的想法是遍历数列，复杂度为O(N)。但目测测试点会给很大的数据规模，暴力检索不可取。

　　于是想到二分搜索，但是调换后的数列不是严格有序的数列，需要做一些微小的工作来特化搜索。

　　首先，考虑没有发生rotate的情况，直接二分查找。可比较首尾元素大小来判断这种情况。

        if nums[h] < nums[t]:
            while h <= t:
                if nums[(h + t) // 2] == target:
                    return (h + t) // 2
                elif nums[(h + t) // 2] < target:
                    h = (h + t) // 2 + 1
                else:
                    t = (h + t) // 2 - 1

　　然后，对于target可能在较大的子列，也就是左边的子列的情况，我们为二分查找多增加一个动作，当查找到的位置在右子列时，直接将尾指针指向那里。可比较那里的元素与首元素大小判断这种情况。

        elif nums[h] < target:
            while h <= t:
                if nums[(h + t) // 2] < nums[h]:
                    t = (h + t) // 2 - 1
                elif nums[(h + t) // 2] == target:
                    return (h + t) // 2
                elif nums[(h + t) // 2] < target:
                    h = (h + t) // 2 + 1
                else:
                    t = (h + t) // 2 - 1

　　对于target可能在右子列的情况，依葫芦画瓢。

        else:
            while h <= t:
                if nums[(h + t) // 2] > nums[t]:
                    h = (h + t) // 2 + 1
                elif nums[(h + t) // 2] == target:
                    return (h + t) // 2
                elif nums[(h + t) // 2] < target:
                    h = (h + t) // 2 + 1
                else:
                    t = (h + t) // 2 - 1

　　需要注意的细节包括两个指针的移动。在覆盖搜索范围的同时确保它们交错，避免死循环和漏查。

　　以下是submission:

 1 class Solution:
 2     def search(self, nums, target):
 3         t = len(nums) - 1
 4         if t == -1:
 5             return -1
 6         elif nums[0] == target:
 7             return 0
 8         elif nums[t] == target:
 9             return t
10         h = 0
11         if nums[h] < nums[t]:
12             while h <= t:
13                 if nums[(h + t) // 2] == target:
14                     return (h + t) // 2
15                 elif nums[(h + t) // 2] < target:
16                     h = (h + t) // 2 + 1
17                 else:
18                     t = (h + t) // 2 - 1
19         elif nums[h] < target:
20             while h <= t:
21                 if nums[(h + t) // 2] < nums[h]:
22                     t = (h + t) // 2 - 1
23                 elif nums[(h + t) // 2] == target:
24                     return (h + t) // 2
25                 elif nums[(h + t) // 2] < target:
26                     h = (h + t) // 2 + 1
27                 else:
28                     t = (h + t) // 2 - 1
29         else:
30             while h <= t:
31                 if nums[(h + t) // 2] > nums[t]:
32                     h = (h + t) // 2 + 1
33                 elif nums[(h + t) // 2] == target:
34                     return (h + t) // 2
35                 elif nums[(h + t) // 2] < target:
36                     h = (h + t) // 2 + 1
37                 else:
38                     t = (h + t) // 2 - 1
39         return -1

　　这种算法的复杂度为log(N)，大概（

　　另安利一种算法，预先使用一次二分来查找子列分割点，复杂度相同，效率稍低，但比较友好。作者为lucastan，传送门https://discuss.leetcode.com/topic/3538/concise-o-log-n-binary-search-solution。

class Solution {
public:
    int search(int A[], int n, int target) {
        int lo=0,hi=n-1;
        // find the index of the smallest value using binary search.
        // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
        // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
        while(lo<hi){
            int mid=(lo+hi)/2;
            if(A[mid]>A[hi]) lo=mid+1;
            else hi=mid;
        }
        // lo==hi is the index of the smallest value and also the number of places rotated.
        int rot=lo;
        lo=0;hi=n-1;
        // The usual binary search and accounting for rotation.
        while(lo<=hi){
            int mid=(lo+hi)/2;
            int realmid=(mid+rot)%n;
            if(A[realmid]==target)return realmid;
            if(A[realmid]<target)lo=mid+1;
            else hi=mid-1;
        }
        return -1;
    }
};