本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題11：旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目要求：
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到末尾成為數(shù)組的旋轉(zhuǎn)棠绘，如1,2,3,4,5=>3,4,5,1,2；0,1,1,1,1=>1,1,1,0,1贼陶；0,1,1,1,1=>1,0,1,1,1阐滩。求一個(gè)原本遞增的數(shù)組旋轉(zhuǎn)后的最小數(shù)字坪稽。
解題思路：
考察二分查找。原本有序扛伍，進(jìn)行了旋轉(zhuǎn)筷畦，但在一定程度上還是有序的。有了這個(gè)出發(fā)點(diǎn)刺洒，如果熟悉二分查找應(yīng)該就離最終結(jié)果差不多了鳖宾。通過(guò)觀察中間點(diǎn)與左右點(diǎn)的關(guān)系，縮小范圍逆航，從而找到最小值鼎文。縮小范圍時(shí)要注意值相等的情況因俐，尤其是左右中三個(gè)值都相等的情況拇惋，這種特殊情況是無(wú)法折半縮小范圍的周偎，只能逐步縮小，即左右點(diǎn)各縮進(jìn)一個(gè)單位蚤假。
此題比較考驗(yàn)邏輯栏饮，明白為什么能用二分查找 && 把各個(gè)ifelse情況理清楚 -> 解決
package chapter2;
/**
* Created by ryder on 2017/6/28.
* 旋轉(zhuǎn)數(shù)組的最小數(shù)字
*/
public class P82_MinNumberInRotatedArray {
public static int min(int[] data){
if(data==null || data.length==0)
return -1;
int left = 0;
int right = data.length-1;
int mid;
while(left<right){
mid = left+(right-left)/2;
//left < right
if(data[left]<data[right])
return data[left];
//left > right
else if(data[left]>data[right]){
if(data[mid]>=data[left])
left = mid + 1;
else
right = mid;
}
//left = right
else{
if(data[left]<data[mid])
left = mid + 1;
else if(data[left]>data[mid])
right = mid;
else{
left = left+1;
right = right-1;
}
}
}
return data[right];
}
public static void main(String[] args){
int[] data1 = {3,4,5,1,2};
int[] data2 = {1,0,1,1,1};
int[] data3 = {1,1,1,0,1};
System.out.println(min(data1));
System.out.println(min(data2));
System.out.println(min(data3));
}
}
運(yùn)行結(jié)果
1
0
0
