题目描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例：
输入：nums = [3,4,5,1,2]
输出：1

题目分析

二分查找，将 mid 的值和第一个元素 first 比较
– 如果比 first 大，说明从 first 到 mid 是递增的，最小值在右侧
– 如果和 first 相等，即第一个元素，只能向右侧搜索（或当前值就是最小值）
– 如果比 first 小，说明最小值在左侧（或当前值就是最小值）

Java

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    int min = nums[0];
    int first = nums[0];
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] >= first) {
            left = mid + 1;
        } else  {
            min = nums[mid];
            right = mid - 1;
        }
    }
    return min;
}

Kotlin

fun findMin(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1
    val first = nums.first()
    var min = first
    while (left <= right) {
        val mid = (left + right) / 2
        if (nums[mid] >= first) {
            left = mid + 1
        } else {
            right = mid - 1
            min = nums[mid]
        }
    }
    return min
}