Search in Rotated Sorted Array

题目地址：
https://leetcode.com/problems/search-in-rotated-sorted-array/#/description

题目：

Suppose an array sorted in ascending order 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.

解题思路：这道题是binary search的变种，需要分两种情况，每种情况分两个部分讨论。
这道题有follow up：如果有duplicate的话，需要加上以下代码：

while(nums[left] == nums[mid] && left != mid){
    left += 1;
}
while(nums[right] == nums[mid] && right != mid){
    right -= 1;
}

代码：

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 + 1 < right){
        int mid = (left + right) / 2;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[left] < nums[mid]){
            if(nums[left] <= target && target < nums[mid]){
                right = mid;
            }
            else{
                left = mid;
            }
        }
        else{
            if(nums[mid] < target && target <= nums[right]){
                left = mid;
            }
            else{
                right = mid;
            }
        }
    }
    if(nums[left] == target){
        return left;
    }
    if(nums[right] == target){
        return right;
    }
    return -1;
}