[Leetcode] 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.

二分搜索的变种题，之前写一直没有搞清楚关系，今天重新写了一次终于算是鼓捣明白了整体的流程。整体过程比较清晰，首先我们判断中值，如果正好相等的话，那么直接返回就好了，而如果不相等的话，我们需要判断目前确定的单调区间以及target是否落在单调区间中来进行二分：

1. 如果A[mid] >= A[l]，这说明从A[l]到A[mid]之间是单调递增的，如果target在这个范围内，那么我们直接搜索这个区间，如果target < A[l] 或者 target > A[mid]，那么说明target不在范围内，所以我们搜索另一个区间
2. 如果A[mid] < A[r]，说明从A[mid]到A[r]之间是单调递增的，同理按照上面的思路来进行搜索

    public int search(int[] A, int target) {
        int l = 0, r = A.length - 1;
        
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(A[mid] == target) return mid;
            else if(A[mid] >= A[l]) { // find the monotone interval
                if(A[mid] > target && target >= A[l]) // located in the monotone interval
                    r = mid - 1;
                else 
                    l = mid + 1;
            }
            else {
                if(A[mid] < target && target <= A[r]) {
                    l = mid + 1;
                }
                else 
                    r = mid - 1;
            }
        }
        
        return -1;
    }