Search In Rotated Sorted Array

搜索旋转排序数组

题目描述

给定一个数组nums和一个整数target。该数组是由升序数组旋转而成，比如[1,2,3,4,5]旋转之后可能变成[4,5,1,2,3]。

请找出target在数组中的索引，如果不存在，返回-1。

示例：

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

解法

解法一：二分法

• 时间复杂度：O(logn)

• 空间复杂度：O(1)

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

解法二：二分法2

该解法很巧妙，主要思想是将不包含target的另一半数组元素，全部设为无穷大或者无穷小。

• 时间复杂度：O(logn)

• 空间复杂度：O(1)

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

        if target < nums[0] && nums[mid] >= nums[0] {
            nums[mid] = math.MinInt64
        }

        if target >= nums[0] && nums[mid] < nums[0] {
            nums[mid] = math.MaxInt64
        }

        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}