劍指 Offer 11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字

把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。

示例 1：

輸入：[3,4,5,1,2]
輸出：1
示例 2：

輸入：[2,2,2,0,1]
輸出：0

解決方法

因?yàn)轭}目中的旋轉(zhuǎn)總會(huì)把最小的元素置于數(shù)組當(dāng)中，所以可以使用二分查找的方法來(lái)尋找最小元素

public class Solution {
    public int MinArray(int[] numbers) {
        int i=0,j=numbers.Length-1;//i與j分別為數(shù)組中最左與最右元素的指針
        while(i<j){
            int m = (i+j) / 2;//m為二分查找中中間元素的指針
            if(numbers[m]>numbers[j])//若中間元素大于最右元素，則代表著中間元素在原數(shù)組的那部分
                i=m+1;//將最左元素指針指向m+1，靠近旋轉(zhuǎn)數(shù)組
            else if(numbers[m]<numbers[j])//若中間元素小于最右元素，代表中間元素在旋轉(zhuǎn)數(shù)組的那部分
                j=m;//將m的位置傳給j，縮小尋找訪問(wèn)
            else
                j--;//此時(shí)代表m值與旋轉(zhuǎn)數(shù)組的最大值相等，需要讓旋轉(zhuǎn)數(shù)組指針-1，這樣循環(huán)才能繼續(xù)下去，這個(gè)步驟不會(huì)影響到查找的準(zhǔn)確性，因?yàn)樾枰檎业氖亲钚?shù)
        }
        return numbers[i];
    }
}