🌕 🌗 33. 搜索旋转排序数组

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    public int search(int[] nums, int target) {
        // 思路：
        // 二分
        int len = nums.length;
        return mySol(nums, target, 0, len - 1);
    }

    private int mySol(int[] nums, int target, int left, int right) {
        // System.out.println(nums[left] + "  " + nums[right]);
        // 递归终止条件
        if(left >= right) {
            if(nums[left] == target) {
                return left;
            } else {
                return -1;
            }
        }
        if(nums[left] == target) {
            return left;
        }
        if(nums[right] == target) {
            return right;
        }
        // left < right
        int mid = left + ((right - left) >> 1); // 偏左的 mid
        if(nums[mid] == target) {
            return mid;
        } 
        // 判断区间是否有旋转点
        if(nums[right] > nums[mid] && nums[mid] >= nums[left]) {
            // 单增
            if(target > nums[mid]) {
                return mySol(nums, target, mid + 1, right); // 右区间
            } else {
                return mySol(nums, target, left, mid - 1);
            }
        }
        // mid 右侧有旋转点，意味着左侧单增
        if(nums[mid] >= nums[left]) {
            if(target > nums[mid]) {
                return mySol(nums, target, mid + 1, right);
            } else {
                // target < [mid]
                if(target > nums[left]) {
                    return mySol(nums, target, left, mid - 1);
                } else {
                    // target < [left]
                    return mySol(nums, target, mid + 1, right);
                }
            }
        }
        // mid 左侧有旋转点，意味着右侧单增
        if(nums[right] > nums[mid]) {
            if(target > nums[mid]) {
                if(target > nums[right]) {
                    return mySol(nums, target, left, mid - 1); // 左
                } else {
                    return mySol(nums, target, mid + 1, right);
                }
            } else {
                return mySol(nums, target, left, mid - 1);
            }
        }
        return -1;
    }
}

---

输出