154.md

Find Minimum in Rotated Sorted Array II

题目:

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.

The array may contain duplicates.

Example 1:
Input: [1,3,5]
Output: 1

Example 2:
Input: [2,2,2,0,1]
Output: 0

思路：

和153的思路大体一致，不同的是数组中带了相同的元素，即一开始不能通过首尾元素判断该数组是否有序。 一开始做一个偏移处理，如果首尾元素相同不断的把后尾索引往前移动，直到不同，后面的逻辑和153相同。

代码：

func findMin(nums []int) int {
    begin, end := 0, len(nums)-1
    for nums[begin] == nums[end] && begin != end {
        end -= 1
    }
    mid := 0
    for nums[begin] > nums[end] {
        mid = (begin + end) / 2
        if nums[begin] <= nums[mid] && nums[mid+1] <= nums[end] {
            if nums[begin] < nums[mid+1]{
                return nums[begin]
            } else {
                return nums[mid+1]
            }
        } else if nums[begin] <= nums[mid] && nums[mid+1] > nums[end] {
            begin = mid + 1
        } else {
            end = mid
        }
    }
    return nums[begin]
}