共计 1426 个字符，预计需要花费 4 分钟才能阅读完成。
题目 ：
整数数组 nums 按升序排列，数组中的值 互不雷同。
在传递给函数之前，nums 在事后未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。
给你 旋转后 的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。
链接：力扣 Leetcode—中级算法—排序和搜寻—搜寻旋转排序数组.
示例 1:
输出：nums = [4,5,6,7,0,1,2], target = 0
输入：4
示例 2：
输出：nums = [4,5,6,7,0,1,2], target = 3
输入：-1
示例 3：
输出：nums = [1], target = 0
输入：-1
标签：数组、二分查找
进阶：你能够设计一个工夫复杂度为 O(log n) 的解决方案吗？
思路 1 ：遍历，有等于 target 就输入，没有返回 -1。
全副 Go 代码如下：
package main
import "fmt"
func search(nums []int, target int) int {n := len(nums)
if n == 0 {return -1} else {
for i, v := range nums {
if v == target {
return i
break
}
}
}
return -1
}
func main() {a := []int{4, 5, 6, 7, 0, 1, 2}
fmt.Println(search(a, 5))
}
提交截图：
思路 2 ：题中进阶做法要求咱们工夫复杂度为 O(log n)，个别就是二分法查找。找出 target 在左半区间的状况 即 target 在[left, mid]
- nums[left] < nums[mid] 即 left-mid 区间 没有旋转 nums[left] <= target <= nums[mid] 则 target 属于左半区间
- nums[left] > nums[mid] 即 left-mid 区间 有旋转 target <= nums[mid] 则 target 属于左半区间
- nums[left] > nums[mid] 即 left-mid 区间 有旋转 target >= nums[left] 则 target 属于左半区间
全副 Go 代码：
package main
import "fmt"
func search(nums []int, target int) int {if len(nums) == 0 {return -1}
left := 0
right := len(nums) - 1
for left <= right {mid := (left + right) / 2
if target == nums[mid] {return mid}
if nums[left] < nums[mid] && target <= nums[mid] && target >= nums[left] {right = mid - 1} else if nums[left] > nums[mid] && target <= nums[mid] {right = mid - 1} else if nums[left] > nums[mid] && target >= nums[left] {right = mid - 1} else {left = mid + 1}
}
return -1
}
func main() {a := []int{4, 5, 6, 7, 0, 1, 2}
fmt.Println(search(a, 5))
}
运行截图：
正文完
