题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

思路

思路一

这个问题很容易让我们往下顺的一个思路，就是中轴在哪里？先从找中轴开始，找到之后，元素在哪边就很容易了，这样两边都是有序的，logn复杂度将不是问题，二分便是。

关键思路就在于 -- 寻找中轴（设为nums[p]）：
中轴特点是什么？左边右边都是升序，且左大于右

详细步骤如下：

1. 用二分法切分数组，

• 如果nums[p+1]小于等于nums[p]，那就说明，恰好p+1就是那个中轴
• 如果nums[p+1]大于nums[p]，那说明p是处在某个升序中，那么下面就是如何判断中轴在左半边还是右半边
  2.判断nums[p] 和 nums[left]的关系，如果nums[p]大，说明p处在左半边，否则在右半边，继续二分即可
  剩下的就简单了。根据边界锁定区域，二分查找即可

思路二

或许，我们没有必要寻找中轴，因为无论如何二分，总至少有一个半边是顺序的，这一点可以根据边际轻松判断出来，所以，二分后，先判断下是不是在顺序区间，再继续二分思路即可

代码

思路一

package main

import "fmt"

func getTargetIndex(nums []int, targetNum int) int {
    if 0 == len(nums) {
        return -1
    }
    centralAxisIndex := getCentralAxisIndex(nums)
    leftIndex, rightIndex := 0, 0

    if nums[0] > targetNum || 0 == centralAxisIndex {
        leftIndex, rightIndex = centralAxisIndex, len(nums)-1
    } else {
        leftIndex, rightIndex = 0, centralAxisIndex-1
    }

    for leftIndex <= rightIndex {
        midIndex := (leftIndex + rightIndex) / 2
        if nums[midIndex] == targetNum {
            return midIndex
        } else if nums[midIndex] > targetNum {
            rightIndex = midIndex - 1
        } else {
            leftIndex = midIndex + 1
        }
    }
    return -1
}

func getCentralAxisIndex(nums []int) int {
    leftIndex, rightIndex := 0, len(nums) - 1
    if nums[leftIndex] <= nums[rightIndex] {
        return 0
    }
    for leftIndex <= rightIndex {
        midIndex := (leftIndex + rightIndex) / 2
        if nums[midIndex+ 1] > nums[midIndex] {
            if nums[leftIndex] < nums[midIndex] {
                leftIndex = midIndex + 1
            } else {
                rightIndex = midIndex
            }
        } else {
            return midIndex + 1
        }
    }
    return 0
}

func main() {
    var nums = []int{4, 5, 6, 7, 8, 0, 1, 2}
    targetNum := 7
    targetIndex := getTargetIndex(nums, targetNum)
    fmt.Println("index: ", targetIndex)
}

思路二

package main

import "fmt"

func getTargetIndex(nums []int, targetNum int) int {
    if len(nums) <= 0 {
        return -1
    }

    leftIndex := 0
    rightIndex := len(nums) - 1
    midIndex := 0

    for leftIndex <= rightIndex {
        midIndex = (leftIndex + rightIndex) / 2
        if nums[midIndex] == targetNum {
            return midIndex
        }

        if nums[midIndex] >= nums[leftIndex] {
            // 边界判断target在哪个区间
            if nums[midIndex] > targetNum && nums[leftIndex] <= targetNum {
                rightIndex = midIndex - 1
            } else {
                leftIndex = midIndex + 1
            }
        } else {
            if nums[midIndex] < targetNum && nums[rightIndex] >= targetNum {
                leftIndex = midIndex + 1
            } else {
                rightIndex = midIndex - 1
            }
        }
    }

    return -1
}

func main() {
    var nums = []int{4, 5, 6, 7, 8, 0, 1, 2}
    fmt.Sprintln(nums)
    targetNum := 71
    targetIndex := getTargetIndex(nums, targetNum)
    fmt.Println("index: ", targetIndex)
}

---

欢迎大家关注我的公众号

半亩房顶