leetcode 33 - Search in Rotated Sorted Array

[zwwhdls]

题意：nums 为升序数组，且以某个未知的未知做了旋转，求 target 在数组中的索引。要求算法复杂度为 O(log(n))

思路：二分法求解，按需判断下一步在左边还是右边

func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }
    left := 0
    right := len(nums) - 1
    for left <= right {
        midd := (left + right) / 2
        if nums[midd] == target {
            return midd
        }

        if target > nums[midd] {
            if nums[left] < nums[midd] || target <= nums[right] {
                left = midd + 1
                continue
            }
            right = midd - 1
        } else {
            if nums[midd] < nums[right] || target >= nums[left] {
                right = midd - 1
                continue
            }
            left = midd + 1
        }
    }
    return -1
}