一、题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1。

二、解题思路

Notzuonotdied的解题思路

最简单的方式就是暴力搜索，但是时间复杂度为$O(n^2)$。这种方式肯定不是我们想要的结果，(⊙v⊙)。正确的方法应该是使用二分查找的方式来找出最小值。

首先，我们先分析下旋转数组的特性。旋转数组可以分为多个子数组，而且每一个子数组都是递增的。同时位于前面的子数组的所有的元素均大于位于后面的子数组中的元素。

根据上面的特性，我们可以得出一个结论：array[preIndex] >= array[postIndex]始终成立。（preIndex代表位于数组前的索引，postIndex代表位于数组后的索引，而且preIndex < postIndex）

之后，我们可以通过计算处于中间位置的索引inIndex，通过比较preIndex，inIndex，postIndex的值得出最小值处于的范围。

比如：当array[inIndex] <= array[postIndex]的时候，最小值位于inIndex的右边；当array[inIndex] >= array[preIndex]的时候，最小值位于inIndex的左边。

看到这里，思维敏捷的你可能会意识到一个问题，假如preIndex，inIndex，postIndex三个索引对应的值相等呢？遇到这种，就只能暴力搜索了……

Kotlin实现

fun main(args: Array<String>) {
    println(findMin(intArrayOf(3, 4, 5, 1, 2)))
}

/**
 * 查找旋转数组中的最小值
 *
 * @param array 旋转数组
 * @return 返回最小值
 * */
fun findMin(array: IntArray): Int {
    // 如果数组为空，就抛出异常
    if (array.isEmpty()) throw Exception("数组不能为空～")

    // 起始索引
    var preIndex = 0
    // 末尾索引
    var postIndex = array.size - 1
    // 中间索引
    var inIndex = preIndex

    // 旋转数组的特性，前面起始递增的部分大于后面递增的部分
    while (array[preIndex] >= array[postIndex]) {
        // 如果只有两个数据的话，就直接返回最后一个
        if (postIndex - preIndex == 1) return array[postIndex]

        // 计算中间值
        inIndex = preIndex + (postIndex - preIndex) / 2

        // 如果三个位置的值是一样的，那就没办法了，只能从头搜索到尾了
        if (array[preIndex] == array[postIndex] && array[preIndex] == array[inIndex]) {
            return array.min()!!
        }

        // 如果最小的值位于inIndex右边的话，3, 4, 5, 1, 2
        if (array[inIndex] >= array[preIndex]) preIndex = inIndex
        // 如果最小的值位于inIndex左边的话，3, 4, 5, 1, 2
        else if (array[inIndex] <= array[postIndex]) postIndex = inIndex
    }
    return array[inIndex]
}

旋转数组求最小值

一、题目

二、解题思路

Notzuonotdied的解题思路

Kotlin实现

输出结果