旋轉數(shù)組的最小數(shù)字

題目描述

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

實現(xiàn)代碼

function minNumberInRotateArray(rotateArray)
{
    var len = rotateArray.length
    if (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];
        }
    }

思路

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

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

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

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

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