Search in Rotated Sorted Array

Q:
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.

A:       目标是找到pivot，并通过线性查找，来找到pivot，然后，才进行正常的二分查找。 这样的复杂度为O(n)

public class Solution {
    public int search(int[] A, int target) {
        // assume A is sorted in ascending order
        if (A.length == 0)
            return -1;
        int pivotIndex = -1;
        // find pivot while searching
        if (A[0] == target) {
            return 0;
        }
        if (A[0] < target) {

            // search the first half part
            int i = 1;
            while (i < A.length) {
                if (A[i] < A[i - 1]) {
                    // i+1 is the pivot,
                    // pivotIndex = i;
                    return -1; // not need to continue search
                }
                if (A[i] == target) {
                    return i;
                } else if (A[i] < target) {
                    i++;
                } else { // A[i] > target
                    return -1; // do not exist in A
                }
            }

        } else { // A[0] > target , ----> search the left half part
                    // find pivot , because the first rotated part are all >
                    // target
            int i = 1;
            while (i < A.length) {
                if (A[i] < A[i - 1]) {
                    pivotIndex = i;
                    break;
                } else {
                    i++;
                }
            }
            // search from pivotIndex;
            i = Math.max(0,pivotIndex);
            while (i < A.length) {
                if (A[i] == target) {
                    return i;
                } else if (A[i] < target) {
                    i++;
                } else { // A[i] > target
                    return -1;
                }
            }
        }
        return -1; // if A[0] > target , and 
                // all values are smaller than target. run this 

    }
}

 Mistakes:
1: 当 A[0] > target 的情况时， 没有考虑找不到pivot 的情况。例如，数组 只有一个值


-------------------第二遍-----------
思想：  对每一个区间 begin 到end .通过对比首尾的值，来确定，是否该区间包含了pivot。
如果不是，则对比A[mid]， 来确定是接下来对比左边，还是右边。
如果A[begin]>= A[end]则包含了pivot节点。我们把两边都查找，并归并结果。

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;
        }
        if(begin == end){
            if(A[begin]==target){
                return begin;
            }else{
                return -1;
            }
        }
        // test whether this section is rotated
        int mid = (begin+end)/2;
        if(A[begin]<A[end]){
            // search only one part
           int left=-1 ,right=-1;// must be clearlly initiallized
            if(A[mid] >=target){ // on left part
                left =  search(A,begin,mid,target);
            }else{ // target lies on right part
                right = search(A,mid+1,end,target);
            }
            return Math.max(left,right);
        }else{ // search both part
            int left =  search(A,begin,mid,target);
            int right = search(A,mid+1,end,target);
            return  Math.max(left,right);
        }
    }
}

---------Mistakes：
1：  for the first case of left and right value,  it must be clearly initialzied,  we cannot assume their default value.


------------------3rd  search both both part directly  ------------------------

public class Solution {
    public int search(int[] A, int target) {
        return search2(A,0,A.length -1, target);
    }
    private int search2(int[] A, int start, int end, int target){
        if(start>end)
            return -1;
        
        int mid = (start+end)/2;
        if( A[mid] == target )
            return mid;
        
        int result = -1;
        if(A[start] >= A[mid] || A[mid]>target)
            result = search2(A,start,mid-1,target);
        
        if(result == -1 &&( A[mid] >= A[end] || A[mid] < target ))
            result = search2(A,mid+1,end,target);
        
        return result;
    }
}