在算法面試中，面試官總是喜歡圍繞鍊錶、排序、二叉樹、二分查找來做文章，而大多數人都可以跟著專業的書籍來做到倒背如流。而面試官並不希望招收的是一位記憶功底很好，但不會活學活用的程序員。所以學會數學建模和分析問題，並用合理的算法或數據結構來解決問題相當重要。
面試題：打印出旋轉數組的最小數字
題目：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3，4，5，1，2} 為數組{1，2，3，4，5} 的一個旋轉，該數組的最小值為1。
要想實現這個需求很簡單，我們只需要遍歷一遍數組，找到最小的值後直接退出循環。代碼實現如下：
public class Test08 { public static int getTheMin(int nums[]) { if (nums == null || nums.length == 0) { throw new RuntimeException("input error!"); } int result = nums[0]; for (int i = 0; i < nums.length - 1; i++) { if (nums[i + 1] < nums[i]) { result = nums[i + 1]; break; } } return result; } public static void main(String[] args) { // 典型輸入，單調升序的數組的一個旋轉int[] array1 = {3, 4, 5, 1, 2}; System.out.println(getTheMin(array1)); // 有重複數字，並且重複的數字剛好的最小的數字int[] array2 = {3, 4, 5, 1, 1, 2}; System.out.println(getTheMin(array2)); // 有重複數字，但重複的數字不是第一個數字和最後一個數字int[] array3 = {3, 4, 5, 1, 2, 2}; System.out.println(getTheMin(array3)); // 有重複的數字，並且重複的數字剛好是第一個數字和最後一個數字int[] array4 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array4)); // 單調升序數組，旋轉0個元素，也就是單調升序數組本身int[] array5 = {1, 2, 3, 4, 5}; System.out.println(getTheMin(array5)); // 數組中只有一個數字int[] array6 = {2}; System.out.println(getTheMin(array6)); // 數組中數字都相同int[] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println(getTheMin(array7)); }}打印結果沒什麼毛病。不過這樣的方法顯然不是最優的，我們看看有沒有辦法找出更加優質的方法處理。
有序，還要查找？
找到這兩個關鍵字，我們不免會想到我們的二分查找法，但不少小伙伴肯定會問，我們這個數組旋轉後已經不是一個真正的有序數組了，不過倒像是兩個遞增的數組組合而成的，我們可以這樣思考。
我們可以設定兩個下標low 和high，並設定mid = (low + high)/2，我們自然就可以找到數組中間的元素array[mid]，如果中間的元素位於前面的遞增數組，那麼它應該大於或者等於low 下標對應的元素，此時數組中最小的元素應該位於該元素的後面，我們可以把low 下標指向該中間元素，這樣可以縮小查找的範圍。
同樣，如果中間元素位於後面的遞增子數組，那麼它應該小於或者等於high 下標對應的元素。此時該數組中最小的元素應該位於該中間元素的前面。我們就可以把high 下標更新到中位數的下標，這樣也可以縮小查找的範圍，移動之後的high 下標對應的元素仍然在後面的遞增子數組中。
不管是更新low 還是high，我們的查找範圍都會縮小為原來的一半，接下來我們再用更新的下標去重複新一輪的查找。直到最後兩個下標相鄰，也就是我們的循環結束條件。
說了一堆，似乎已經繞的雲裡霧裡了，我們不妨就拿題幹中的這個輸入來模擬驗證一下我們的算法。
我們再來看看Java 中如何用代碼實現這個思路：
public class Test08 { public static int getTheMin(int nums[]) { if (nums == null || nums.length == 0) { throw new RuntimeException("input error!"); } // 如果只有一個元素，直接返回if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid; // 確保low 下標對應的值在左邊的遞增子數組，high 對應的值在右邊遞增子數組while (nums[low] >= nums[high]) { // 確保循環結束條件if (high - low == 1) { return nums[high]; } // 取中間位置mid = (low + high) / 2; // 代表中間元素在左邊遞增子數組if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } public static void main(String[] args) { // 典型輸入，單調升序的數組的一個旋轉int[] array1 = {3, 4, 5, 1, 2}; System.out.println(getTheMin(array1)); // 有重複數字，並且重複的數字剛好的最小的數字int[] array2 = {3, 4, 5, 1, 1, 2}; System.out.println(getTheMin(array2)); // 有重複數字，但重複的數字不是第一個數字和最後一個數字int[] array3 = {3, 4, 5, 1, 2, 2}; System.out.println(getTheMin(array3)); // 有重複的數字，並且重複的數字剛好是第一個數字和最後一個數字int[] array4 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array4)); // 單調升序數組，旋轉0個元素，也就是單調升序數組本身int[] array5 = {1, 2, 3, 4, 5}; System.out.println(getTheMin(array5)); // 數組中只有一個數字int[] array6 = {2}; System.out.println(getTheMin(array6)); // 數組中數字都相同int[] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println(getTheMin(array7)); // 特殊的不知道如何移動int[] array8 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array8)); }}前面我們提到在旋轉數組中，由於是把遞增排序數組的前面的若干個數字搬到數組後面，因為第一個數字總是大於或者等於最後一個數字，而還有一種特殊情況是移動了0 個元素，即數組本身，也是它自己的旋轉數組。這種情況本身數組就是有序的了，所以我們只需要返回第一個元素就好了，這也是為什麼我先給result 賦值為nums[0] 的原因。
上述代碼就完美了嗎？我們通過測試用例並沒有達到我們的要求，我們具體看看array8 這個輸入。先模擬計算機運行分析一下：
但我們一眼了然，明顯我們的最小值不是1 ，而是0 ，所以當array[low]、array[mid]、array[high] 相等的時候，我們的程序並不知道應該如何移動，按照目前的移動方式就默認array[mid] 在左邊遞增子數組了，這顯然是不負責任的做法。
我們修正一下代碼：
public class Test08 { public static int getTheMin(int nums[]) { if (nums == null || nums.length == 0) { throw new RuntimeException("input error!"); } // 如果只有一個元素，直接返回if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid = low; // 確保low 下標對應的值在左邊的遞增子數組，high 對應的值在右邊遞增子數組while (nums[low] >= nums[high]) { // 確保循環結束條件if (high - low == 1) { return nums[high]; } // 取中間位置mid = (low + high) / 2; // 三值相等的特殊情況，則需要從頭到尾查找最小的值if (nums[mid] == nums[low] && nums[mid] == nums[high]) { return midInorder(nums, low, high); } // 代表中間元素在左邊遞增子數組if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } /** * 查找數組中的最小值* * @param nums 數組* @param start 數組開始位置* @param end 數組結束位置* @return 找到的最小的數字*/ public static int midInorder(int[] nums, int start, int end) { int result = nums[start]; for (int i = start + 1; i <= end; i++) { if (result > nums[i]) result = nums[i]; } return result; } public static void main(String[] args) { // 典型輸入，單調升序的數組的一個旋轉int[] array1 = {3, 4, 5, 1, 2}; System.out.println(getTheMin(array1)); // 有重複數字，並且重複的數字剛好的最小的數字int[] array2 = {3, 4, 5, 1, 1, 2}; System.out.println(getTheMin(array2)); // 有重複數字，但重複的數字不是第一個數字和最後一個數字int[] array3 = {3, 4, 5, 1, 2, 2}; System.out.println(getTheMin(array3)); // 有重複的數字，並且重複的數字剛好是第一個數字和最後一個數字int[] array4 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array4)); // 單調升序數組，旋轉0個元素，也就是單調升序數組本身int[] array5 = {1, 2, 3, 4, 5}; System.out.println(getTheMin(array5)); // 數組中只有一個數字int[] array6 = {2}; System.out.println(getTheMin(array6)); // 數組中數字都相同int[] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println(getTheMin(array7)); // 特殊的不知道如何移動int[] array8 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array8)); }}我們再用完善的測試用例放進去，測試通過。
總結
本題其實考察的點挺多的，實際上就是考察對二分查找的靈活運用，不少小伙伴死記硬背二分查找必須遵從有序，而沒有學會這個二分查找的思想，這樣會導致只能想到循環查找最小值了。
不少小伙伴在面試中表態，Android 原生態基本都封裝了常用算法，對面試這些無作用的算法表示抗議，其實這是相當愚蠢的。我們不求死記硬背算法的實現，但求學習到其中巧妙的思想。只有不斷地提升自己的思維能力，才能助自己收穫更好的職業發展。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。