LeetCode讲解篇之33. 搜索旋转排序数组

题目描述

题目链接

题解思路

旋转后的数组具备一个特性，如果把数组分割成两部分，必定至少有一部分是递增的，并且其中递增区间可以通过左端点小于右端点这个特征来确定

我们基于这个特性，进行二分查找数组时，判断递增区间是左区间还是右区间
然后基于该递增区间进行剪枝

• 如果target不在我们确定的递增区间中，则舍弃该递增区间的后续查找
• 如果target在我们确定的递增区间中，则舍弃另一个区间的后续查找

题解代码

func search(nums []int, target int) int {n := len(nums)if n < 2 {if nums[0] == target {return 0}return -1}l, r := 0, n - 1for l <= r {mid := (l + r) >> 1if nums[mid] == target {return mid}// 若 l == mid，意味着 [l, r] 这个区间内只有两个元素，检查该区间内是否存在目标值if l == mid {if nums[r] == target {return r}return -1}if nums[l] < nums[mid] {// 左区间 l ~ mid 为递增区间if nums[l] <= target && target < nums[mid] {// 目标值在递增区间内r = mid - 1} else {// 目前值不在递增区间内l = mid + 1}} else {// 右区间 mid ~ r 为递增区间if nums[mid] < target && target <= nums[r] {// 目标值在递增区间内l = mid + 1} else {// 目标值不在递增区间内r = mid - 1}}}// 二分搜索未找到目标值，返回-1return -1
}