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.

---

It is the same idea as binary search. But we need to add some more cases to consider. If the left part is in ascending order and target may be found in this part. Do binary search on this part to find the target. If it is not, just find the target in the right part.

C++ Code:

/*
 * func: search_rotated_sorted_array_helper
 * goal: helper function of search_rotated_sorted_array
 * @param A: input integer array
 * @param start: start index of the array
 * @param end: end index of the array
 * @param target: target value
 * return the index of the target, if not exist, return -1
 */
int search_rotated_sorted_array_helper(int A[], int start, int end, int target){
    if(start >= end){
        return A[start] == target ? start : -1;
    }
    int mid = start + (end-start)/2;
    if(target == A[mid]){
        return mid;
    }else if(A[mid] >= A[start]){
        if(A[start] <= target && target < A[mid]){
            return search_rotated_sorted_array_helper(A, start, mid-1, target);
        }else{
            return search_rotated_sorted_array_helper(A, mid+1, end, target);
        }
    }else{
        if(A[mid] < target && target <= A[end]){
            return search_rotated_sorted_array_helper(A, mid+1, end, target);
        }else{
            return search_rotated_sorted_array_helper(A, start, mid-1, target);
        }
    }
}
/*
 * func: search_rotated_sorted_array
 * goal: find the target value in a rotated sorted array
 * @param A: input integer array
 * @param n: size of array
 * @param target: target value
 * return: the index of the target, if not exist, return -1
 */
/*
 * same idea as binary search, just need different conditions
 * complexity: time O(log n), space O(1)
 */
int search_rotated_sorted_array(int A[], int n, int target){
    assert(n > 0);
    return search_rotated_sorted_array_helper(A, 0, n-1, target);
}

Python Code:

# func: search a target in a rotated sorted array
# @param A: integer list A
# @param target: target value
# complexity: time O(log n), space O(1)
def search_rotated_sorted_array(A, target):
    start = 0
    end = len(A) - 1
    while start <= end:
        mid = start + (end-start)/2
        if A[mid] == target:
            return mid
        #If the left part is in ascending order
        elif A[start] <= A[mid]:
            #If the target may be in the normal order part
            if A[start] <= target < A[mid]:
                end = mid-1
            else:
                start = mid+1
        else:
            if A[mid] < target <= A[end]:
                start = mid+1
            else:
                end = mid-1
    return -1