漫畫：知乎面試題（旋轉數組最小值Ⅱ – 進階版）
- 2020 年 3 月 30 日
- 筆記
今天是小浩算法「365刷題計劃」第72天。繼續為大家講解二分法系列篇 – 旋轉排序數組最小值Ⅱ（進階版）。話不多說，直接看題：
01 PART
旋轉排序數組最小值Ⅱ
昨天為大家講解了元素不可重複的版本，那如果元素重複該如何處理呢？
第154題：假設按照升序排序的數組在預先未知的某個點上進行了旋轉。( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。請找出其中最小的元素。
注意數組中可能存在重複的元素。
示例 1：
輸入: [1,3,5]
輸出: 1
示例 2：
輸入: [2,2,2,0,1]
輸出: 0
說明：
這道題是 尋找旋轉排序數組中的最小值 的延伸題目。
允許重複會影響算法的時間複雜度嗎？會如何影響，為什麼？
02 PART
題目回顧
之前我也說過，通過改變題中條件，使得題目難度上升的做法。在算法題目的設計中，是一種非常常見的手段。本題就是這樣，從中等變成了困難。
（通過改變題目，使得難度上升）
在講解本題之前，首先要對昨天的題目進行一個答疑。昨天有人問我為什麼題目中講的是與left進行比較，但是最後代碼中寫的時候變成了和right比較。這個確實是我講的時候講忘了，但是這其實是一個思維轉化的問題：因為在旋轉之前的原數組是一個遞增序列，那一定是左邊的數小，右邊的數大，而我們要找的是最小值，所以比較偏向左找。那如果和left進行比較，其實也是完全ok的，那我們的思路就變成了找到偏右的最大值，進而向右再移動一位，自然也就是最小值。如果不能理解的話，可以回顧一下昨天的文章：
並且我這裡對昨天的題目，補上一個和left對比的版本，供大家參考學習（昨天沒有給Go的示例，所以今天補一個Go的）
//go func findMin(nums []int) int { left, right := 0, len(nums)-1 for left < right { mid := left + (right-left)>>1 + 1 if nums[left] < nums[mid] { left = mid } else if nums[left] > nums[mid] { right = mid - 1 } } return nums[(right+1)%len(nums)] }
上面的代碼有兩處需要說明，第一：mid中最後加1的目的，是為了使得mid更加靠近right，增加容錯性。當然，你寫到裡邊也是可以的，甚至更好。我怕大家看不懂，所以寫在外面了。第二：最後一行代碼取模，是需要考慮最大值剛好在最右邊的情況。
03 PART
題解分析
二分查找的本質，其實就是通過收斂查找空間，找到目標值的一種方式。請大家認真閱讀這句話。不管是採用不同的mid定義方式，又或者是不一樣的while條件，統統都是為了這個目的。在完成這個目的的基礎上，我們才去考慮如何減少冗餘代碼，減少循環次數等等，完成進一步的優化。
現在再來看今天的題目。相對比昨天題目而言，其實只是多了nums[mid] 等於 nums[right] 時的額外處理。（當然， 如果是和left進行比較，就是nums[mid]等於nums[left]）
對比一下下面兩個圖：
其實直接就可以給出代碼了：
//java class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { left = mid + 1; } else if (nums[mid] < nums[right]) { right = mid; } else { right--; } } return nums[left]; } };
鄭重申明（讀我的文章必看）：
- 本系列所有教程都不會用到複雜的語言特性，大家無須擔心沒有學過相關語法，算法思想才是最重要的！
- 作為學術文章，雖然風格可以風趣，但嚴謹，我是認真的。本文所有代碼均在leetcode進行過測試運行。
如果我們再對比一下代碼的差異，就會非常的明顯：
（左邊是有重複，右邊是無重複）
可以看到在 nums[mid] 等於 nums[right] 時的情況下，我們只多了一個 right-1 的操作。這裡需要額外說明的是，為什麼要這樣做？我看leetcode上的題解，這塊很多都是長篇大論，其實沒那麼複雜，一句話就可以給你講明白，看看下面這個！
因為 mid 和 right 相等時，最小值既可能在左邊，又可能在右邊，所以此時自然二分思想作廢，咱們就砍掉一個右邊界。說白了，就是讓子彈再飛一會兒。
