0153.find-minimum-in-rotated-sorted-array.md

0153.Find-Minimum-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]).

Find the minimum element.

You may assume no duplicate exists in the array. Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

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

Tags: Math, String

题意

现有一个有序数组，假设从某个数开始将它后面的数按顺序放到了数组前面。 (即 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2])。 请找出数组中的最小元素。 数组中不包含重复元素。

题解

思路1

(二分) O(logn)

处理这种问题有个常用技巧：如果不想处理边界情况，比如当数组只有两三个数的时候，代码会出问题。我们可以在数组长度太短(这道题中我们判断数组长度小于5)时，直接暴力循环做；数组有一定长度时再用二分做。 这样做并不会影响算法的时间复杂度，但会缩短写代码的时间。 为了便于理解，我们将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：

我们会发现数组中最小值前面的数 nums[i]nums[i] 都满足：nums[i]≥nums[0]nums[i]≥nums[0]，其中 nums[n−1]nums[n−1] 是数组最后一个元素；而数组中最小值后面的数（包括最小值）都不满足这个条件。 所以我们可以二分出最小值的位置。 另外，不要忘记处理数组完全单调的特殊情况。 时间复杂度分析：二分查找，所以时间复杂度是 O(logn)O(logn)。

func findMin(nums []int) int {
    if nums[len(nums)-1] > nums[0] {
        return nums[0]
    }
    l, r := 0, len(nums)-1
    for l < r {
        mid := l + (r-l)>>1
        if nums[mid] >= nums[0] {
            l = mid + 1
        } else {
            r = mid
        }
    }

    return nums[l]
}

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm