题目：
整数数组 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 mainimport "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 mainimport "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))}

运行截图：