LeetCode 面试题 10.03. 搜索旋转数组

Categories:

题目描述
思路分析
1. 解法一：二分查找（处理重复元素）（推荐）
相似题目

题目描述

✅ 面试题 10.03. 搜索旋转数组

思路分析

解法一：二分查找（处理重复元素）（推荐）

核心思路：

旋转数组仍由两个有序区间组成，但存在重复元素时无法判断有序区间。

若 nums[left] == nums[mid] == nums[right]，只能收缩边界。

其余情况与经典旋转数组二分一致。

复杂度分析：

时间复杂度：O(log n)（平均），O(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] && nums[mid] == nums[right]) {
                left++;
                right--;
            } else 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] && nums[mid] == nums[right] {
			left++
			right--
		} else 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
}

相似题目

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/53346308