搜索旋转排序数组

一、leetcode 33. 搜索旋转排序数组

题目描述（题目难度，中等）

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

题目求解

解法一

先二分查找数组中最大值的位置，将数组分成两个升序子数组，再在目标值所在的子数组内二分查找目标值。

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if(len == 0) return -1;
        int low = 0, high = len-1, mid = 0;
        while(low < high) {
            mid = (low+high) >>> 1;
            if(mid+1 <= high && nums[mid] > nums[mid+1]) break;
            if(nums[mid] > nums[high]) low = mid+1;
            else high = mid;
        }
        // 未旋转的情况
        if(low == high) return binarySearch(nums, 0, len-1, target);
        if(nums[len-1] < target) return binarySearch(nums, 0, mid, target);
        else return binarySearch(nums, mid+1, len-1, target);
    }
    private int binarySearch(int[] nums, int low, int high, int target) {
        int mid;
        while(low <= high) {
            mid = (low+high) >>> 1;
            if(nums[mid] < target) low = mid+1;
            else if(nums[mid] > target) high = mid-1;
            else return mid;
        }
        return -1;
    }
}

解法二

直接改造二分查找。

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length-1, mid;
        while(low <= high){
            mid = (low+high) >>> 1;
            if(nums[mid] < target){
                // 中值在右区间，目标值在左区间，需左移
                if(nums[low]>nums[mid] && nums[low]<=target) high = mid-1;
                // 正常情况，右移
                else low = mid+1;
            }else if(nums[mid] > target){
                // 中值在左区间，目标值在右区间，需右移
                if(nums[low]<=nums[mid] && nums[low]>target) low = mid+1;
                // 正常情况，左移
                else high = mid-1;
            }else return mid;
        }
        return -1;
    }
}

对比来看的话，解法二应该更优一点。

二、leetcode 81. 搜索旋转排序数组 II

题目描述（题目难度，中等）

这是上一题的延伸题目，和上一题的区别是，本题中的 nums 可能包含重复元素。

题目求解

由于本题中的 nums 包含重复元素，所以当 nums[mid] == nums[low] == nums[high] 时，nums[mid] 没办法根据 nums[low] 或 nums[high]，确定 mid 当前是处于左升序区间还是右升序区间。
例如，[2, 2, 2, 3, 2] 和 [2, 1, 2, 2, 2]。

我的解决方案是，首先通过指数搜索，快速找到第一个不等于 nums[nums.length-1] 的值，如果没找到，就老老实实顺序查找，否则，就采用上一题的思路，继续查找。

class Solution {
    public boolean search(int[] nums, int target) {
        int i = 0, len = nums.length;
        while(i < len && nums[i] == nums[len-1]) i = (i+1) << 1;
        if(i >= len) {
            // 顺序查找
            for(i = 0; i < len; ++i) {
                if(nums[i] == target) return true;
            }
            return false;
        }else if(i == 0){
            return search0(nums, 0, len-1, target);
        }else {
            if(nums[i] < nums[len-1] && nums[i] > target) {
                // 这种情况，搜索左边区间即可
                return search0(nums, (i>>1)-1, i, target);
            }
            if(nums[i] > nums[len-1] && nums[i] < target) {
                // 这种情况，搜索右边区间即可
                return search0(nums, i, len-1, target);
            }
            return search0(nums, i, len-1, target)
                    || search0(nums, (i>>1)-1, i, target);
        }
    }
    private boolean search0(int[] nums, int floor, int ceil, int target) {
        int low = floor, high = ceil, mid;
        while(low <= high){
            mid = (low+high) >>> 1;
            if(nums[mid] == target) return true;
            if(nums[mid] < target){
                // 中值在右区间，目标值在左区间，需要左移
                if(nums[low] > nums[mid] && nums[low] <= target) high = mid-1;
                // 正常情况下的右移
                else low = mid+1;
            }else{
                // 中值在左区间，目标值在右区间，需要右移
                if(nums[low] <= nums[mid] && nums[low] > target) low = mid+1;
                // 正常情况下的左移
                else high = mid-1;
            }
        }
        return false;
    }
}