题目描述#

给定一个原本升序排列、且元素互不相同的整数数组 nums。数组在某个未知下标处发生了旋转，例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]。

现在需要在旋转后的数组里查找 target。如果存在，就返回它的下标；如果不存在，就返回 -1。题目要求时间复杂度为 O(log n)，所以还是得请二分查找上场啦～

旋转数组看起来像队伍被拧了一下，咱先盯住哪半边还整整齐齐～

思路#

普通二分依赖整个数组有序，但旋转之后，整体不再有序。不过别慌，拜托，旋转排序数组有个很可爱的性质：每次取 mid 之后，[left, mid] 和 [mid, right] 这两半里，至少有一半一定是有序的。

所以每轮先判断哪边有序。如果 nums[left] <= nums[mid]，说明左半边 [left, mid] 是升序的；这时只要判断 target 是否落在 nums[left] <= target < nums[mid] 之间。如果在，就把 right 收到 mid - 1；如果不在，就去右半边找。

反过来，如果左半边不是有序的，那右半边 [mid, right] 一定是有序的。此时判断 target 是否满足 nums[mid] < target <= nums[right]。如果满足，就让 left = mid + 1；否则就把 right = mid - 1。没错没错，这题不是“直接比较 target 和 mid”，而是先拍清楚哪一半路是直的，再决定往哪边跑。

只要每轮都能丢掉一半区间，复杂度就仍然是 O(log n)。照片当然不是现实，但把每一段有序区间都拍下来，混乱也会慢慢露出线索呢。好啦，咱继续往下看代码，咔嚓！

思维边界#

• 元素互不相同：因此可以用 nums[left] <= nums[mid] 稳定判断左半边是否有序，不需要处理重复元素带来的歧义。
• 左半边有序：如果 nums[left] <= target && target < nums[mid]，目标一定在左半边，否则去右半边。
• 右半边有序：如果 nums[mid] < target && target <= nums[right]，目标一定在右半边，否则去左半边。
• 边界包含关系：因为 nums[mid] == target 已经提前返回，所以后续区间判断中一边使用严格小于，避免把 mid 重复算进去。
• 查找失败：当 left > right 时，说明所有可能区间都被排除了，返回 -1。

本姑娘小提示：先找有序半边，再判断 target 在不在里面，稳啦～

代码#

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
}