旋轉數組的最小數字

題目描述

　　把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。
　　輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。
　　NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。

---

實現代碼

function minNumberInRotateArray(rotateArray) {var len = rotateArray.lengthif (len == 0){return 0}else{ var low = 0;var high = len-1;while(low<high){var mid = low + Math.floor((high - low) / 2); if(rotateArray[mid] > rotateArray[high]){low = mid + 1;}else if(rotateArray[mid] == rotateArray[high]){high = high - 1;}else{high = mid;} }return rotateArray[low];}}

思路

　　旋轉之后的數組實際上可以劃分成兩個有序的子數組：前面子數組的大小都大于后面子數組中的元素，實際上最小的元素就是兩個子數組的分界線。

我們用兩個指針low和high分別指向數組的第一個元素和最后一個元素。按照題目的旋轉的規則，第一個元素應該是大于等于最后一個元素的；但是如果不是旋轉，第一個元素肯定小于或等于最后一個元素。

找到數組的中間元素。中間元素大于最后一個元素，則中間元素位于前面的遞增子數組，此時最小元素位于中間元素的后面。我們可以讓第一個指針low指向中間元素。

中間元素小于最后一個元素，則中間元素位于后面的遞增子數組，此時最小元素位于中間元素的前面。我們可以讓第二個指針high指向中間元素。

中間元素等于最后一個元素，則將第二個指針向前移，然后繼續比較。

轉載于:https://www.cnblogs.com/echovic/p/6430643.html

總結

以上是生活随笔為你收集整理的《剑指offer》— JavaScript（6）旋转数组的最小数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。