每天一道算法题

LeetCode第33题：搜索旋转排序数组

这道题其实比较简单，排序好的数组，首先想到的就是二分查找，即便他挪过，那么二分最起码有一半是有序的，就可以判定出数据在不在这一半中间，则每一次递归都可以排除掉一半的数据，最终达到O(logN)的复杂度。

/**
     * 解法：二分查找法，二分后一半有序，一半无序。有序那部分可以直接判断，不在范围内则舍弃那半部分
     */
    public static int search2(int[] nums, int target) {
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            // 左右两组其中一组有序
            if (nums[left] < nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                if (target > nums[mid] && target <= nums[right - 1]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }
        return -1;
    }