题目

给定一个升序排序数组 nums，这个数组有可能在某一 k 处被旋转了，例如 [4,5,6,7,0,1,2]。k 为 3
对于这个排序数组 nums，我们给定一个目标数 target。判断 target 是否在数组中。是返回位置，不是，返回 -1。

解析

对于一个旋转后的排序数组来说
如果从前往后遍历，是递增的，并且总会遇到一个突然递减的数。
如果从后往前遍历，是递减的，并且总会遇到一个突然递减的数。

判断 target 和 head tail 的大小
如果比 head 大往前遍历，直到遇到 target 或突然减小的数字
如果比 tail 小往后遍历，直到遇到 target 或突然增大的数字
如果比 head 小，但是比 tail 大，说明不存在。

伪代码

idx = -1
if target > head
  for i<len && nums[i] > nums[i-1]
    if nums[i] == target
        idx = i
        break
 if target < tail
    for i>=0 && nums[i] < nums[i+1]
      if nums[i] == target
          idx = i
          break
return idx

代码

func search(nums []int, target int) int {
    idx := -1
    if target == nums[0] {
        return 0
    }
    if target == nums[len(nums)-1] {
        return len(nums)-1
    }
    if target > nums[0] {
        for i:=1; i<len(nums) && nums[i] > nums[i-1] ; i++ {
            if nums[i] == target {
                idx = i
                break
            }
        }
    }
    if target < nums[len(nums)-1] {
        for i:=len(nums)-2; i>=0 && nums[i] < nums[i+1]; i-- {
            if nums[i] == target {
                idx = i
                break
            }
        }
    }
    return idx
}

image.png