题意：给定一个数组和目标值，数组原本是升序排序，在下标k处做旋转操作后数组变为nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]。要求判断数组内是否存在目标值，并且算法的时间复杂度控制在O(logn)以内。

33. Search in Rotated Sorted Array (opens new window)

在排序好的数组里搜某个值可以使用二分查找，本题的数组实际是拆分成了两个排好序的部分，二分查找时，中间值的落点可能不在排好序的部分。需要先判断中间值是否在排好序的部分，因为二分查找的前提是数组是排好序的。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = -1;
        while (left <= right) {
            mid = (left + right)/2;
            if (nums[mid] == target) {
                return mid;
            }
            // 判断left到mid是否是排好序的部分
            if (nums[left] <= nums[mid]) {
                // 判断目标值是否在该区间里
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            if (nums[mid] <= nums[right]) {
                if (nums[mid] <= target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}