Search in Rotated Sorted Array

search.java

/*
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.

Algorithm:
1. Check if the mid is located in the left part or not, for example: 3, 4, 5, 1, 2, mid: 5, return true
2. When mid is in the left part of the array
    a. if target > A[mid], then target will be on the right side of mid
    b. if target < A[mid], then we need to check the left most A[left] and target
        1. if A[left] > target, then target will be on the right side
        2. else then target will be on the left side
3. When mid is in the right part of the array
    a. if target > A[mid], then we need to check the right most A[right] and target
        1. if A[right] > target, then target will be on the right side
        2. else then target will be on the left side of the array
    b. if target < A[mid], then the target will be on the left side
4. return if A[mid] == target
*/
public class Solution {
    public int search(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int left = 0;
        int right = A.length - 1;
        while(right >= left) {
            int mid = (right + left) / 2;
            if(isLeftPart(mid, A, right)) {
                if(A[mid] > target) {
                    if(target < A[left]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                } else if(A[mid] < target) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            } else {
                if(A[mid] > target) {
                    right = mid - 1;
                } else if(A[mid] < target) {
                    if(target > A[right]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }
    
    public boolean isLeftPart(int mid, int[] A, int right) {
        if(A[mid] >= A[right]) return true;
        else return false;
    }
}