LintCode 題解丨微軟面試題：尋找旋轉排序數組中的最小值

假設一個排好序的數組在其某一未知點發生了旋轉（比如​0 1 2 4 5 6 7​ 可能變成​4 5 6 7 0 1 2​）。你需要找到其中最小的元素。

線上評測位址：

LintCode 領扣

​

樣例 1:

輸入：[4, 5, 6, 7, 0, 1, 2]

輸出：0

解釋：

數組中的最小值為0

樣例 2:

輸入：[2,1]

輸出：1

數組中的最小值為1

解題思路

• 最直接的是暴力解法，搜尋整個數組找到最小元素，時間複雜度為O(n)。

  我們可以旋轉數組的特性，用改進後的二分查找來解決，時間複雜度為O(logn)。

算法流程

使用二分法來尋找最小值，如圖所示可以幫助我們了解算法過程。

設定雙指針​left​和​right​指向數組​nums​兩端。

第一次分類讨論：比較​nums[left]​和​nums[right]​

如果​nums[left] < nums[right]​，說明數組沒有旋轉過，仍然是升序排列。我們直接​return nums[left]​。

反之，說明數組非單調，進入到第二次分類讨論。

第二次分類讨論：比較​nums[left]​和​nums[mid]​，其中​mid​是二分中點。

如果​nums[left] > nums[mid]​，可以證明此時數組右半邊是升序的，那我們就不用考慮右半邊了。最小值一定在​[left, mid]​間，令​right = mid​。

如果​nums[left] <= nums[mid]​，可以證明此時數組左半邊是升序的，于是我們不需要考慮左半邊。最小值一定在​(mid, right]​間，令​left = mid + 1​。

直到​left == right​時，此時指向的就是最小值，​return nums[left]​。

等效方法

上述算法中，第二次分類讨論我們比較的是​nums[left]​和​nums[mid]​的大小關系，其實比較​nums[right]​和​nums[mid]​的大小也是一樣的。

​nums[left] > nums[mid]​，等效于​nums[mid] < nums[right]​

​nums[left] <= nums[mid]​，等效于​nums[mid] > nums[right]​

有興趣可以證明一下。代碼如何實作，看個人的preference啦。

複雜度分析

時間複雜度: O(log(n))，n為​nums​的長度。同二分查找的時間複雜度。

空間複雜度: $O(1) $。沒有使用額外空間。

public class Solution {

/**
 * @param nums: a rotated sorted array
 * @return: the minimum number in the array
 */
public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    // 二分法
    while (left < right){
        // 最小值在left
        if (nums[left] < nums[right]){
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        // 最小值在[left, mid]
        if (nums[left] > nums[mid]){
            right = mid;
        }
        // 最小值在(mid, right]
        else{
            left = mid + 1;
        }
    }
    return nums[left];
}           

}

更多題解參考：

九章算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時線上授課為你傳授面試技巧