Rotated Sorted Array Search

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

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.

Input : [4 5 6 7 0 1 2] and target = 4
Output : 0

思路：

Binary search. there are four cases:
1. left part is sorted, and target is in the left part
2. left part is sorted, but target is in the right part
3. right part is sorted, and target is in the right part
4. right part is sorted, but target is in the left part

To determine whether left part or right is part is sorted, we can compare value of mid index with left index and right index.
To determine whether target is in a sorted part, we simply check if target is in the range.
Note that when comparing mid value with left value and right value, we need to use "<=" or ">=" because it is possible we are picking the same element for mid index and left/right index, in that case, that part is still considered sorted. For example, when searching for 1 in [3, 1], in the first round, 3 (left) <= 3 (mid), so we decide left part is sorted and target is not in left, so we continue searching in the right part.

Solution:

Time: O(logn)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE LIST
    public int search(final List<Integer> a, int b) {
        int left = 0;
        int right = a.size() - 1;
        int target = b;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int leftVal = a.get(left);
            int rightVal = a.get(right);
            int midVal = a.get(mid);
            // System.out.println("midVal: " + midVal);
            // System.out.println("leftVal: " + leftVal);
            // System.out.println("rightVal: " + rightVal);

            if (midVal == target) {
                return mid;
            } else if (midVal >= leftVal && leftVal <= target && target < midVal) {
                // left half is sorted, and target is in left
                right = mid - 1;
            } else if (midVal >= leftVal) {
                // left half is sorted, but target is in right
                left = mid + 1;
            } else if (midVal <= rightVal &&  midVal < target && target <= rightVal) {
                // right half is sortad and target is in right
                left = mid + 1;
            } else {
                // right half is sorted, but target is in left
                right = mid - 1;
            }
            // System.out.println("~~~~~~~~~~~~~~");
        }
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] <= target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}