33. Search in Rotated Sorted Array

这道题虽然被标记为hard，但其实不是太难。感觉leetcode给出的难度不是特别靠谱，还是看AC率准确些。

如果是已经排序好的数组，直接binary search就可以了。但这个数组在某个点被反转了，我的第一反应是先找出反转的点，然后在数组有序的部分上再次binary search。找反转点的过程也是一次binary search。下图中的7就是一个反转点。

于是有了第一个解法：

public class Solution {
    public int search(int[] nums, int target) {
        // nums中没有重复，就简化很多
        if (nums == null || nums.length == 0)
            return -1;
        if (nums.length == 1)
            return nums[0] == target ? 0 : -1;

        // 第一次binary search，找到反转点
        // binary search时，最让人讨厌的就是inclusive和exclusive的问题，每次都要很小心的处理
        // 我是全部下标都是inclusive的
        int begin = 0, end = nums.length - 1;
        while (begin < end - 1) {  // 注意这个终止条件，最终结果应该是end-begin=1，begin是反转点
            int mid = (begin + end) / 2;
            if (nums[mid] > nums[end]) {
                begin = mid;  // 反转点在mid右边
            } else {
                end = mid;   // 反转点在mid左边
            }
        }
        //System.out.println(begin+","+end);
        // begin是反转点
        // 然后binary search找到目标，直接用了Arrays.binarySearch方法
        // 注意Arrays.binarySearch如果找不到目标，会返回负数，但不一定是-1
        int tmp = -1;
        // 整个数组是由有序的2部分组成的，要在哪部分上搜索？
        if (target >= nums[0] && target <= nums[begin])
            tmp = Arrays.binarySearch(nums, 0, begin + 1, target);
        else
            tmp = Arrays.binarySearch(nums, begin + 1, nums.length, target);

        return tmp < 0 ? -1 : tmp;
    }
}

这个解法虽然能AC，但是只能beat 1.5%，也就是说差一点就TLE的节奏。。。后来看了其他人的一些解法，发现其实不必两次binary search的，一次就可以，于是改进了下我的代码，有了第二个解法：

public class Solution {
    public int search(int[] nums, int target) {
        // nums中没有重复，就简化很多
        if (nums == null || nums.length == 0)
            return -1;
        if (nums.length == 1)
            return nums[0] == target ? 0 : -1;

        int begin = 0, end = nums.length - 1;
        // 同样注意inclusive和exclusive的问题
        while (begin < end) {
            int mid = (begin + end) / 2;
            if (nums[mid] == target)
                return mid;
            // 左侧有序，右侧无序
            if (nums[mid] > nums[end]) {
                if (target >= nums[begin] && target <= nums[mid])
                    end = mid - 1;
                else
                    begin = mid + 1;
            }
            // 左侧无序，右侧有序
            else {
                if (target >= nums[mid] && target <= nums[end])
                    begin = mid + 1;
                else
                    end = mid - 1;
            }
        }

        return nums[begin] == target ? begin : -1;
    }
}

第二个解法也比较好理解，只是要在经典的binary search基础上加一些判断条件。不过也只能beat 5.3%。。。

其实这道题还有些衍生问题：1.如果数组中有重复元素，应该如何处理？2.如果数组不是由一个有序数组rotate而来，而是由两个有序数组拼成的，比如[1,2,3,2,3,4,5,6]，又该如何处理？