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.

Naive Way: 这是我算法课期中考试的一道原题，日，当时我没做出来。在一个sorted array里查找Binary search是O(logn)， 那么它如果rotated了一下还能否O(logn)呢。（关于binary search做法的题目，这章文章最下面有链接。）画一张图就很清楚了，有以下两种情况：

示例图

1.  当处于第一种情况时， target 介于[b1,e1）之间，对前半部分进行search, target <= e2 和 target >= b2 ，对后半分布进行search. 注意到e1, b2是连着的，e2,b1也是连着的。
2. 当处于第二种情况时， target介于（b2, e2]之间， 对后半部分search，否则search 前半部分。

      如何区分这两种情况，可以比较e1和e2，也可以比较b1和b2。


public class Solution {
    public int search(int[] A, int target) {
        return search(A,0,A.length-1,target);
    }
    
    private int search(int[] A, int begin, int end, int target){
        if(begin > end)
            return -1;
        int middle = (begin+end)/2;
        if(A[middle]==target)
            return middle;
        if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                return search(A, begin, middle-1, target);
            else
                return search(A, middle+1, end, target);
        }else{
            if(A[middle] < target && A[end] >= target)
                return search(A, middle+1, end, target);
            else
                return search(A, begin, middle-1, target);
        }
    }
}

关于binary search的题目还有Search-in-rotated-sorted-array-ii, Search-insert-position