LeetCode 33. 搜索旋转排序数组

Categories:

Tags:

题目描述
思路分析
1. 解法一：二分查找（判断有序区间）（推荐）
2. 解法二：先找旋转点 + 二分
相似题目

题目描述

✅ 33. 搜索旋转排序数组

题目：

整数数组 nums 按升序排列且元素互不相同。在某个未知下标 k 处进行了旋转，变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。给定旋转后的数组和目标值 target，若存在则返回其下标，否则返回 -1。要求时间复杂度 O(log n)。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中每个值都独一无二
-10^4 <= target <= 10^4

思路分析

解法一：二分查找（判断有序区间）（推荐）

核心思路：

旋转数组仍由两个有序区间组成。

每次二分后，至少有一半区间是有序的。

通过判断 nums[left] <= nums[mid] 确定哪一半有序，再判断目标是否落在有序区间内，从而缩小搜索范围。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

// 二分判断有序区间
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

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

            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

// 二分判断有序区间
func search(nums []int, target int) int {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}

		if nums[left] <= nums[mid] {
			// 左半部分有序
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			// 右半部分有序
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	return -1
}

解法二：先找旋转点 + 二分

核心思路：

先用二分找到最小值下标（旋转点）。

根据目标与末尾元素的大小关系，决定在哪个有序区间进行标准二分查找。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

// 先找旋转点再二分
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int rot = findRotation(nums);

        if (target >= nums[rot] && target <= nums[n - 1]) {
            return binarySearch(nums, rot, n - 1, target);
        }
        return binarySearch(nums, 0, rot - 1, target);
    }

    private int findRotation(int[] nums) {
        int left = 0;
        int 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;
    }

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

// 先找旋转点再二分
func search(nums []int, target int) int {
	rot := findRotation(nums)
	if target >= nums[rot] && target <= nums[len(nums)-1] {
		return binarySearch(nums, rot, len(nums)-1, target)
	}
	return binarySearch(nums, 0, rot-1, target)
}

func findRotation(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] > nums[right] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

func binarySearch(nums []int, left, right, target int) int {
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

相似题目

题目	难度	考察点
81. 搜索旋转排序数组 II	中等	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找
154. 寻找旋转排序数组中的最小值 II	困难	二分查找
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找
704. 二分查找	简单	二分查找
162. 寻找峰值	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/77306570