旋转数组搜索

📌 问题描述

在旋转排序数组中搜索目标值。

旋转数组：将有序数组从某个位置断开，将前半部分移到后面。

例如：

• 原数组：[1, 2, 3, 4, 5, 6, 7]
• 旋转后：[4, 5, 6, 7, 1, 2, 3]（从索引3断开）

💻 算法实现

LeetCode 33 - 搜索旋转排序数组（无重复）

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
}

LeetCode 81 - 搜索旋转排序数组 II（有重复）

func searchWithDuplicates(nums []int, target int) bool {
    left, right := 0, len(nums)-1
 
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }
 
        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 false
}

🎯 算法演示

搜索 [4, 5, 6, 7, 0, 1, 2] 中的目标值 0：

步骤1: [4, 5, 6, 7, 0, 1, 2]
        L           M           R
        nums[3]=7 != 0
        nums[0]=4 <= nums[3]=7（左半有序）
        target=0不在[4,7)之间，搜索右半部分

步骤2:             [0, 1, 2]
                    L  M  R
        nums[5]=1 != 0
        nums[4]=0 <= nums[5]=1（左半有序）
        target=0在[0,1)之间，搜索左半部分

步骤3:             [0]
                    L=M=R
        nums[4]=0 == 0，找到！

结果: 索引4

💡 核心思想

关键观察

旋转数组有一个特点：至少有一半是有序的

[4, 5, 6, 7, 0, 1, 2]
 -------有序---  --有序-

左半[4,5,6,7]有序，右半[0,1,2]也有序

判断有序部分

if nums[left] <= nums[mid] {
    // 左半部分有序
} else {
    // 右半部分有序（因为旋转点在左半部分）
}

判断target所在位置

在有序的那一半中，用标准二分查找的判断方法：

if nums[left] <= target && target < nums[mid] {
    // target 在有序的左半部分
} else {
    // target 在右半部分
}

🔗 相关题目

LeetCode 153 - 寻找旋转排序数组中的最小值

func findMin(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 nums[left]
}

LeetCode 154 - 寻找旋转排序数组中的最小值 II（有重复）

func findMinWithDuplicates(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 if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

📊 复杂度分析

情况	时间复杂度	说明
无重复元素	O(log n)	标准二分查找
有重复元素（最坏）	O(n)	所有元素相同时退化
有重复元素（平均）	O(log n)	大部分情况仍是对数

💡 技巧总结

1. 找有序部分：比较 nums[left] 和 nums[mid]
2. 判断target位置：在有序部分用标准二分判断
3. 处理重复元素：当 nums[left] == nums[mid] == nums[right] 时，缩小边界

📚 相关主题

• 标准二分查找 - 二分查找基础
• 寻找峰值 - 另一种非完全有序的二分查找

---

返回：搜索算法