Leetcode - Search in Rotated Sorted Array

[分析] 这题可以看做是Find Minimum in Rotated Sorted Array 的扩展，思路仍然是二分，若mid 元素正好是target，皆大欢喜找到了，否则就需要进一步推理target 如果在数组中存在应该在左半边还是右半边，推理思路是：若左边界元素小于mid元素，说明左半边是升序的，查看左边界是否是target，否则若target 落在左边界和mid元素限定的范围内则继续搜左半边，否则搜右半边；若左边界大于mid元素，说明右半边是升序的，类似处理。

[ref]
http://blog.csdn.net/linhuanmars/article/details/20525681

public class Solution {
    public int search(int[] A, int target) {
        if(A == null || A.length < 1)        
            return -1;
        
        int lp = 0, rp = A.length - 1;
        while(lp <= rp){
            int mid = lp + ((rp - lp) >> 1);
            if(A[mid] == target)
                return mid;
            if(A[mid] > A[lp]){
                if(A[lp] == target)
                    return lp;
                else if(A[lp] < target && target < A[mid])
                    rp = mid - 1;
                else
                    lp = mid + 1;
            }else{
                if(A[rp] == target)
                    return rp;
                else if(A[mid] < target && target < A[rp])
                    lp = mid + 1;
                else
                    rp = mid - 1;
            }
        }
        return -1;
    }
}