Search in Rotated Sorted Array

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

假设有一个升序的数组，但是从某处出现了旋转。 要在此数组中查找给定值，并且时间复杂度为O(log n)。

Solution

此题为二分查找法的一个变形：

跟二分查找法一样，先找出中间数，判断是否命中。

如果未命中，则根据大小判断是落在左边还是右边。

当我们找出中间数之后，需要确定哪一边是完全升序的数组。然后判断目标是否落在该区域，以决定接下来在哪边进行查找。

// 递归写法
func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    mid := len(nums) / 2

    if nums[mid] == target {
        return mid
    }

    search_right := func() int {
        r := search(nums[mid:], target)
        if r == -1 {
            return -1
        }
        return mid + r
    }

    search_left := func() int {
        return search(nums[:mid], target)
    }

    // 判断左边是否有序
    if nums[0] < nums[mid] {
        // 左边有序时判断是否在左边范围
        if target >= nums[0] && target <= nums[mid] {
            return search_left()
        }

        return search_right()
    } else {
        // 右边有序时判断是否在右边范围
        if target >= nums[mid] && target <= nums[len(nums) - 1] {
            return search_right()
        }

        return search_left()
    }
}

Similar Problem