搜索旋转排序数组

难度：⭐⭐⭐ 面试高频

考点

• 二分查找变体
• 判断有序区间
• 字节面试高频题

题目描述

整数数组 nums 按升序排列（值互不相同），在传递给函数之前在某个未知下标 k 处进行了旋转（例如 [0,1,2,4,5,6,7] 在 k=4 处旋转变为 [4,5,6,7,0,1,2]）。

给你旋转后的数组 nums 和整数 target，如果 target 在数组中，返回其下标；否则返回 -1。

函数签名

func search(nums []int, target int) int

示例

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

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

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

要求

1. 时间复杂度 O(logn)
2. 不能先找旋转点再分段二分（面试中追问时需要一次二分解决）

提示

• 每次二分后，必有一半是有序的
• 判断 target 是否在有序的那一半中
• nums[left] <= nums[mid] → 左半有序

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

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 target >= nums[left] && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else { // 右半部分有序
			if target > nums[mid] && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}