##把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉， 輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素， 例如陣列{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該陣列的最小值為1， NOTE：給出的所有元素都大于0，若陣列大小為0，請回傳0，
思路
二分查找，此處查找有兩個終止條件，一是傳統的查找結束，二是提前搜索完某一子段，
時間復雜度O(lgn)，空間復雜度O(1)，
代碼
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length < 1) return 0;
int start = 0;
int end = array.length - 1;
int mid = 0;
while(start < end) {
if(array[start] < array[end]) return array[start];
mid = (start + end) / 2;
if(array[start] < array[mid]) {
start = mid + 1;
} else if(array[mid] < array[end]) {
end = mid;
} else {
start++;
}
}
return array[start];
}
}
筆記
與普通的二分查找不同，該題某一子段被用完需要提前退出，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90059.html
標籤：其他
上一篇：耗材銷售尋找防盜版方式