劍指Offer 圖解 | 尋找旋轉排序數組中的最小值

下面開始今天的學習～

今天分享的題目來源于 LeetCode 上第 153 号問題：尋找旋轉排序數組中的最小值。也是《劍指Offer》上的一道經典題。

題目描述

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組  [0，1，2，4，5，6，7] 可能變為 [4，5，6，7，0，1，2] )。

請找出其中最小的元素。

你可以假設數組中不存在重複元素。

示例 1:

輸入: [3，4，5，1，2]
輸出: 1      

示例 2:

輸入: [4，5，6，7，0，1，2]
輸出: 0      

題目解析

這道題目最簡單粗暴的方式就是 直接周遊 整個數組來尋找，這個方法的時間複雜度為 O(N)，空間複雜度為 O(1) 。

不過，這樣來做的話完全沒有利用到題目給出一個條件 旋轉 。

事實上，可以考慮将時間複雜度從 O(n) 縮小到 O(lgn)，這時候 二分查找法 就浮現在腦海。

當然，這裡是 二分查找法 的一種變體。

更多有關二分查找法的文章點選這篇：​​一網打盡！二分查找解題模版與題型全面解析​​

二分的方法可以保證每次比較後，去掉數組中一半的元素。

這道題目中可以将 中點 與 終點 進行比較。

• ​

  ​mid​

  ​​ < ​

  ​end​

  ​：最小值在左半部分。
• ​

  ​mid​

  ​​ > ​

  ​end​

  ​：最小值在右半部分。

也就是說隻需要把 mid 和 end 比較，mid < end 丢棄右半部分（更新 end = mid），mid > end 丢棄左半部分（ 更新 start = mid + 1）。

直到 end 等于 start 時候結束就可以了。

補充：之是以這裡 更新 start = mid + 1 而不是 start = mid 是因為存在一種特殊情況。當數組隻剩兩個元素的時候，​

​mid = （start + end）/ 2​

​​，​

​mid​

​​ 取的就是 ​

​start​

​​。然後如果此時 ​

​mid > end​

​​，會發現 ​

​start​

​ 的位置不會變化，出現 死循環。（可以通過以下動畫加深了解）

動畫描述

代碼實作

//author:程式員吳師兄
//source:圖解面試算法
class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) return nums[low];
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]){
               low = mid + 1; 
            } else{
               high = mid;
            } 
          }
        return nums[low];
    }
}      

複雜度分析

• 時間複雜度：和二分搜尋一樣O(logN)
• 空間複雜度：O(1)

相關題目推薦

• LeetCode 33：搜尋旋轉排序數組
• LeetCode 154：尋找旋轉排序數組中的最小值 II