题目

给定一个经过旋转的升序数组和目标值，返回目标值下标；若不存在，返回 -1。

题目分析

这题虽然是二分，但难点不在传统的“比大小缩区间”，而在于你要先判断：

  • 左半边是否有序
  • 右半边是否有序

因为旋转之后，至少有一边仍然保持有序。

方法一：直觉解法

暴力扫描当然可以做，但这题的价值就在于练习“带条件判断的二分查找”。

方法二：优化思路

每次取 mid 后：

  • 如果 nums[left] <= nums[mid]，说明左半边有序
  • 否则右半边有序

再根据 target 是否落在有序区间里，决定保留哪一半。

Go 实现

 1func search(nums []int, target int) int {
 2    left, right := 0, len(nums)-1
 3    for left <= right {
 4        mid := left + (right-left)/2
 5        if nums[mid] == target {
 6            return mid
 7        }
 8
 9        if nums[left] <= nums[mid] {
10            if nums[left] <= target && target < nums[mid] {
11                right = mid - 1
12            } else {
13                left = mid + 1
14            }
15        } else {
16            if nums[mid] < target && target <= nums[right] {
17                left = mid + 1
18            } else {
19                right = mid - 1
20            }
21        }
22    }
23    return -1
24}

复杂度分析

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

易错点

  • 判断哪边有序时，不要忘记带等号
  • 条件区间要和保留区间严格对应，否则很容易丢答案

我的复盘

这题让我意识到：很多“变种二分”并不是新模板，而是在二分骨架上额外叠一层区间语义判断。