11.md

旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

示例

输入 [3,4,5,1,2] 返回值 1

思路

二分查找，关键在于旋转前的数组非递减排序，即递增但是会有相同的连续值

实现

package main

import "fmt"

func main() {
	rotateArray := []int{3, 6, 5, 1, 2}
	res := minNumberInRotateArray(rotateArray)
	fmt.Println(res)
}

func minNumberInRotateArray(rotateArray []int) int {
	if len(rotateArray) == 0 {
		return 0
	}
	low := 0
	high := len(rotateArray) - 1
	for {
		if low >= high {
			break
		}
		mid := (high + low) / 2
		if rotateArray[mid] > rotateArray[high] {
			// 中位大于高位，低位是中位后一位
			low = mid + 1
		} else if rotateArray[mid] < rotateArray[high] {
			// 中位小于高位，高位置为当前中位
			high = mid
		} else {
			if rotateArray[high-1] > rotateArray[high] {
				// 高位前一位大于高位，最小值即使当前高位
				low = high
				break
			}
			// 连续相同值的情况，高位向前推进一步
			high -= 1
		}
	}
	return rotateArray[low]
}