LeetCode 33. 搜索旋转排序数组

33. 搜索旋转排序数组

解题思路

利用 153. 寻找旋转排序数组中的最小值 思路

根据旋转数组中最小元素的索引，去判断 target 在左区间还是右区间，最后进行二分查找

参考代码

class Solution {
    public int search(int[] nums, int target) {
        int midIndex = findMinIndex(nums);
        int n = nums.length;
        // target 大于最右值 → 在左半段 [0, midIndex-1]
        if (target > nums[n-1]) {
            return binarySearch(nums, target, 0, midIndex - 1);
        } 
        // 否则在右半段 [midIndex, n-1]
        else {
            return binarySearch(nums, target, midIndex, n - 1);
        }
    }

    private int binarySearch(int[] nums, int target, int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    private int findMinIndex(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}