链接

题目.

难度:

high

解答：

我们可以分成2步来解决问题

找出旋转点，可以用二分法，即找到第一个小于nums[0]的索引在合适的数组里面二分查找 本来用一次二分就可以查找到，但是这个判断逻辑搞复杂了，不如2次二分清晰 package main import "fmt" func search(nums []int, target int) int { if len(nums) == 0 { return -1 } if len(nums) == 1 { if nums[0] == target { return 0 } return -1 } low, high := 0, len(nums)-1 if nums[low] > nums[high] { for low < high { mid := (low + high) / 2 fmt.Println(low, mid, high) if nums[mid] < nums[0] { high = mid } else { low = mid + 1 } } } fmt.Println("pivot", low) if target >= nums[low] && target <= nums[len(nums)-1] { high = len(nums) - 1 } else { low, high = 0, low-1 } fmt.Println("searching", low, high) for low <= high { mid := (low + high) / 2 if nums[mid] == target { return mid } if target < nums[mid] { high = mid - 1 } else { low = mid + 1 } } return -1 } func main() { nums := []int{1, 3, 5} fmt.Println(search(nums, 1)) }

复杂度分析

time

O(logn)

space

O(1)

执行结果

执行用时 :4 ms, 在所有 golang 提交中击败了81.01%的用户 内存消耗 :2.6 MB, 在所有 golang 提交中击败了61.70%的用户