LeetCode81(2021.4.7)

LC81. 搜索旋转排序数组 II

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }

        //恢复二段性,否则无法二分
        int l = 0, r = n - 1;
        while (l < r && nums[0] == nums[r]) {
            r--;
        }
        int mr = r;

        //二分找旋转点
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) {
                l = mid;
            }
            else {
                r = mid - 1;
            }
        }

        if (target >= nums[0]) {
            l = 0;
        }
        else {
            l++;
            r = mr;
            if (l > r) {
                return false;
            }
        }

        //二分求解
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        return nums[l] == target;
    }
}

留下评论