把一個數組最開始的若幹個元素搬到數組的末尾,我們稱之為數組的旋轉。
輸入一個非遞減排序的數組的一個旋轉,輸出旋轉數組的最小元素。
例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉,該數組的最小值為1。
NOTE:給出的所有元素都大于0,若數組大小為0,請傳回0。
思路,原始數組為有序數組,考慮用二分。
普通的二分思路為,給定遞增數組,給定target,循環條件為low<high,比較mid和target的值大小,如果mid>target,則high=mid-1;如果mid<target,low = mid + 1。
這次沒有target,要找最小值,那就比較兩端的值,比較high值。
注意此處有3個取值,mid<high;mid==high;mid>high;
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int low = 0;
int high = array.length - 1;
int mid = 0;
while(low < high){
mid = (low + high) / 2;
if(array[mid] < array[high]){ // 3 1 2 此時mid為最小值
high = mid;
}else if(array[mid] == array[high]){ //1 1 1 0 1
high = high - 1 ;
}else{ // 3 4 5 1 2
low = mid + 1;
}
}
return array[low];
}
}