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.

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

http://www.lintcode.com/en/problem/search-in-rotated-sorted-array/

Discussion

跟普通的binary search问题不同的地方在于，我们只能在rotated sorted array的有序的两段上应用二分查找，因此首先判断那段是有序的，再决定在有序的那一段上update start/end by mid。

Solution

class Solution {
    /** 
     * param A : an integer ratated sorted array
     * param target :  an integer to be searched
     * return : an integer
     */
public:
    int search(vector<int> &A, int target) {
        // write your code here
        int n = A.size();
        if(n ==0) return -1;
        int start = 0; 
        int end = n-1;
        int mid;
        while(start + 1 <end) {
            mid = start + (end-start)/2;
            if(A[mid] == target)
                return mid;
            if(A[start] < A[mid]) {//前半段有序？
                if(A[start] <= target && target <= A[mid]) {
                    end = mid;//target在前半段，截去后半段
                } else {
                    start = mid;
                }
            } else {//后半段有序？
                if(A[mid] <= target && target <= A[end]) {
                    start = mid;//target在后半段，截去前半段
                } else {
                    end = mid;
                }
            }
        }
        if(A[start] == target)//跟经典二分查找一样，看最终的start和end哪一个是target
            return start;
        if(A[end] == target) 
            return end;
        return -1;
    }
};

以上solution是假定array里是没有重复元素的，所以if(A[mid] == target) return mid;,如果有重复元素并且要求返回第一次出现的index，是不能在这里return的。去掉这句话，把下一句if(A[start] < A[mid]) 改为if(A[start] <= A[mid])即可。example [3, 3, 3, 4, 3, 3], target = 3.这样能优先保证在前半段查找。所以一定要沟通沟通沟通，不要上来就傻乎乎想当然的做题。。。。

做了Search in Rotated Sorted Array II才发现上面那一段分析是错误的，报错的case是[9,5,6,7,8,9,9,9,9,9,9], 8。错在哪里呢，我的例子里if(A[start] <= A[mid])能保证前半段递增，其实这是不对的，比如报错的这个例子。。。

那怎样才能保证递增呢？当然是A[start] < A[mid]了，这时候在前半段二分查找，同样的道理A[start] < A[mid]时在后半段二分查找，当A[start] == A[mid]呢？如果题目只是要求返回target出现的任一位置或者是否存在，直接start++，若要求返回出现的第一个位置，先看A[start]是否为target再start++。

Solution 见Search in Rotated Sorted Array II.

Update

以上统统想的太复杂了。先用二分查找找到pivot出现的地方,参加问题Find Minimum in Rotated Sorted Array II，再在前后两段分别应用二分查找找target就行了。

class Solution {
    /** 
     * param A : an integer ratated sorted array
     * param target :  an integer to be searched
     * return : an integer
     */
public:
    int search(vector<int> &A, int target) {
        if(A.empty()) return -1;
        int start = 0;
        int end = A.size() - 1;
        //1. find the index of pivot
        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if(A[mid] < A[end]) {
                end = mid;
            } else if(A[mid] > A[end]){
                start = mid; 
            }
        }
        int pivot = -1;
        if(A[start] < A[end]) pivot = start;
        else pivot = end;
        //2. apply binary search for both parts
        int idx = binarySearch(A, 0, pivot - 1, target);
        if(idx != -1) return idx;
        else return binarySearch(A, pivot, A.size() - 1, target);
    }
    int binarySearch(vector<int> &A, int start, int end, int target) {
        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if(A[mid] < target) {
                start = mid;
            } else {
                end =  mid;
            }
        }
        if(A[start] == target) return start;
        if(A[end] == target) return end;
        return -1;
    }
};