搜索旋转排序数组

搜索旋转排序数组（LeetCode 33）

数组原本有序，在某个位置被旋转。要求 O(log n) 查找目标值。

核心思路

二分时，至少有一半是有序的，利用这一性质缩小范围。

public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {        // 左半段有序
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                             // 右半段有序
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

搜索旋转排序数组 II（LeetCode 81，含重复元素）

有重复时无法保证某半段严格有序，遇到 nums[lo] == nums[mid] 时，lo++ 跳过。

public boolean search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return true;
        if (nums[lo] == nums[mid]) {    // 无法判断哪半有序
            lo++;
        } else if (nums[lo] < nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return false;
}

最坏时间复杂度：O(n)（全为相同元素时）；平均 O(log n)。

寻找旋转排序数组中的最小值（LeetCode 153/154）

无重复（153）

public int findMin(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;
        } else {
            hi = mid;      // nums[mid] 可能是最小值，不能 mid-1
        }
    }
    return nums[lo];
}

有重复（154）

public int findMin(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;
        } else if (nums[mid] < nums[hi]) {
            hi = mid;
        } else {
            hi--;           // 无法判断，缩小右边界
        }
    }
    return nums[lo];
}

查找旋转点（旋转次数）

// 找旋转索引（最小值下标即旋转次数）
public int findRotateIndex(int[] nums) {
    if (nums[0] < nums[nums.length - 1]) return 0;
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[mid + 1]) return mid + 1;
        if (nums[mid] < nums[lo]) hi = mid - 1;
        else lo = mid + 1;
    }
    return 0;
}

三题对比