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

[solution].java

public class Solution {
    public int search(int[] A, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        return search(A, target, 0, A.length - 1);
    }
    
    public int search(int[] A, int target, int begin, int end){
        if(begin > end) return -1;
        
        int midle = (begin + end) / 2;
        if(target == A[midle]) return midle;
        if(A[midle] >= A[begin]){
            if(target < A[midle]){
                if(target >= A[begin])
                    return search(A, target, begin, midle - 1);
                else return search(A, target, midle + 1, end);
            }
            else return search(A, target, midle + 1, end);
        }
        else{
            if(target < A[midle])
                return search(A, target, begin, midle - 1);
            else{
                if(target >= A[begin])
                    return search(A, target, begin, midle - 1);
                else return search(A, target, midle + 1, end);
            }
        }
    }
}