力扣第33题-搜索旋转排序数组

题目
题目链接

题解

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        return specialBinarySearch(nums, target, 0, nums.length - 1);
    }

    /**
     * 非排序数组二分查找
     * @param nums 数组
     * @param target 目标
     * @param left 左起点
     * @param right 右起点
     * @return 目标下标，-1为没找到
     */
    private int specialBinarySearch(int[] nums, int target, int left, int right) {
        if (nums == null || nums.length < 1 || left < 0 || right < 0 || left > right || left > nums.length - 1 || right > nums.length - 1) {
            return -1;
        }
        if (right == left && nums[right] == target) {
            return right;
        }
        for (int l = left, r = right, mid = (l + r) / 2; l <= r;) {
            // 判断原数组0下标在mid左侧还是右侧
            if (nums[mid] < nums[r]) {
                // 在mid左侧或者命中mid
                // target与nums[mid]比较
                if (target > nums[mid]) {
                    // nums[0] < target < 原nums[0] || nums[mid] < taget < nums[len - 1]
                    // 查找右侧
                    int index = binarySearch(nums, target, mid, r);
                    if (index != -1) {
                        return index;
                    } else {
                        // nums[mid] < taget < nums[len - 1] 不成立，那只可能是 nums[0] < taget < 原nums[0]，重新选举mid
                        // 下一步查找左侧
                        r = mid;
                        mid = (l + r) / 2;
                        if (l + 1 >= r) {
                            if (target == nums[l]) {
                                return l;
                            } else if (target == nums[r]) {
                                return r;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else if (target < nums[mid]) {
                    // 原nums[0] < target < mid，重新选举mid
                    // 下一步查找左侧
                    r = mid;
                    mid = (l + r) / 2;
                    if (l + 1 >= r) {
                        if (target == nums[l]) {
                            return l;
                        } else if (target == nums[r]) {
                            return r;
                        } else {
                            return -1;
                        }
                    }
                } else {
                    return mid;
                }
            } else {
                // 在mid右侧
                // target与nums[mid]比较
                if (target < nums[mid]) {
                    // nums[0] < target < nums[mid] || 原nums[0] < target < nums[len - 1]
                    int index = binarySearch(nums, target, l, mid);
                    if (index != -1) {
                        return index;
                    } else {
                        // nums[0] < target < nums[mid]不成立，确定目标在：原nums[0] < target < nums[len - 1]
                        // 下一步查找右侧
                        l = mid;
                        mid = (l + r) / 2;
                        if (l + 1 >= r) {
                            if (target == nums[l]) {
                                return l;
                            } else if (target == nums[r]) {
                                return r;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else if (target > nums[mid]) {
                    // nums[mid] < target < 原nums[0]
                    // 下一步查找右侧
                    l = mid;
                    mid = (l + r) / 2;
                    if (l + 1 >= r) {
                        if (target == nums[l]) {
                            return l;
                        } else if (target == nums[r]) {
                            return r;
                        } else {
                            return -1;
                        }
                    }
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }

    /**
     * 普通二分查找
     * @param nums 数组
     * @param target 目标
     * @param left 左起点
     * @param right 右起点
     * @return 目标下标，-1为没找到
     */
    private int binarySearch(int[] nums, int target, int left, int right) {
        if (nums == null || nums.length < 1 || left < 0 || right < 0 || left > right || left > nums.length - 1 || right > nums.length - 1) {
            return -1;
        }
        if (right == left && nums[right] == target) {
            return right;
        }
        for (int l = left, r = right, mid = (l + r) / 2; l <= r;) {
            if (target > nums[mid]) {
                l = mid;
            } else if (target < nums[mid]) {
                r = mid;
            } else {
                return mid;
            }
            mid = (l + r) / 2;
            if (l + 1 >= r) {
                if (nums[l] == target) {
                    return l;
                } else if (nums[r] == target) {
                    return r;
                } else {
                    return -1;
                }
            }
        }
        return -1;
    }
}