33. 搜索旋转排序数组（高频题）

33. 搜索旋转排序数组

• 解题思路
• 代码

解题思路

本质上还是有序数组嘛，所以用二分搜索。

1. 首先找到旋转点
2. 将数组在逻辑上从旋转点切分成两个有序数组
3. 分别对两个有序数组进行二分搜索即可

代码

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int spinPoint = findMin(nums);
        int left1 = 0;
        int right1 = spinPoint - 1;

        while (left1 <= right1) {

            int mid = left1 + (right1 - left1) / 2;
            if (nums[mid] > target) {
                right1 = mid - 1;
            } else if (nums[mid] < target) {
                left1 = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            }

        }

        int left2 = spinPoint;
        int right2 = nums.length - 1;
        while (left2 <= right2) {
            int mid = left2 + (right2 - left2) / 2;
            if (nums[mid] > target) {
                right2 = mid - 1;
            } else if (nums[mid] < target) {
                left2 = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        //不存在
        return -1;
    }


    //找到旋转点的下标
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            if (left == right) {
                break;
            }
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}