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

題目： 把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾， 我們稱之數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)， 輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3，4, 5, 1, 2 ｝為｛ l1,2,3, 4，5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為 1。

實現(xiàn)代碼如下：

[java] view plaincopyprint?
public class Test08 {    
    /** 
     * 把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾， 我們稱之數(shù)組的旋轉(zhuǎn)。 
     * 輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 
     * 例如數(shù)組{3, 4, 5, 1, 2｝為｛l ,2, 3, 4, 5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為 
     * 
     * @param numbers 旋轉(zhuǎn)數(shù)組 
     * @return 數(shù)組的最小值 
     */  
    public static int min(int[] numbers) {  
        // 判斷輸入是否合法  
        if (numbers == null || numbers.length == 0) {  
            throw new RuntimeException("Invalid input.");  
        }  
        // 開始處理的第一個位置  
        int lo = 0;  
        // 開始處理的最后一個位置  
        int hi = numbers.length - 1;  
        // 設置初始值  
        int mi = lo;  
        // 確保lo在前一個排好序的部分，hi在排好序的后一個部分  
        while (numbers[lo] >= numbers[hi]) {  
            // 當處理范圍只有兩個數(shù)據(jù)時，返回后一個結(jié)果  
            // 因為numbers[lo] >= numbers[hi]總是成立，后一個結(jié)果對應的是最小的值  
            if (hi - lo == 1) {  
                return numbers[hi];  
            }  
            // 取中間的位置  
            mi = lo + (hi - lo) / 2;  
            // 如果三個數(shù)都相等，則需要進行順序處理，從頭到尾找最小的值  
            if (numbers[mi] == numbers[lo] && numbers[hi] == numbers[mi]) {  
                return minInorder(numbers, lo, hi);  
            }  
            // 如果中間位置對應的值在前一個排好序的部分，將lo設置為新的處理位置  
            if (numbers[mi] >= numbers[lo]) {  
                lo = mi;  
            }  
            // 如果中間位置對應的值在后一個排好序的部分，將hi設置為新的處理位置  
            else if (numbers[mi] <= numbers[hi]) {  
                hi = mi;  
            }  
        }  
        // 返回最終的處理結(jié)果  
        return numbers[mi];  
    }  
    /** 
     * 找數(shù)組中的最小值 
     * 
     * @param numbers 數(shù)組 
     * @param start   數(shù)組的起始位置 
     * @param end     數(shù)組的結(jié)束位置 
     * @return 找到的最小的數(shù) 
     */  
    public static int minInorder(int[] numbers, int start, int end) {  
        int result = numbers[start];  
        for (int i = start + 1; i <= end; i++) {  
            if (result > numbers[i]) {  
                result = numbers[i];  
            }  
        }  
        return result;  
    }  
    public static void main(String[] args) {  
        // 典型輸入，單調(diào)升序的數(shù)組的一個旋轉(zhuǎn)  
        int[] array1 = {3, 4, 5, 1, 2};  
        System.out.println(min(array1));  
        // 有重復數(shù)字，并且重復的數(shù)字剛好的最小的數(shù)字  
        int[] array2 = {3, 4, 5, 1, 1, 2};  
        System.out.println(min(array2));  
        // 有重復數(shù)字，但重復的數(shù)字不是第一個數(shù)字和最后一個數(shù)字  
        int[] array3 = {3, 4, 5, 1, 2, 2};  
        System.out.println(min(array3));  
        // 有重復的數(shù)字，并且重復的數(shù)字剛好是第一個數(shù)字和最后一個數(shù)字  
        int[] array4 = {1, 0, 1, 1, 1};  
        System.out.println(min(array4));  
        // 單調(diào)升序數(shù)組，旋轉(zhuǎn)0個元素，也就是單調(diào)升序數(shù)組本身  
        int[] array5 = {1, 2, 3, 4, 5};  
        System.out.println(min(array5));  
        // 數(shù)組中只有一個數(shù)字  
        int[] array6 = {2};  
        System.out.println(min(array6));  
        // 數(shù)組中數(shù)字都相同  
        int[] array7 = {1, 1, 1, 1, 1, 1, 1};  
        System.out.println(min(array7));  
        System.out.println(min(array6));  
        // 輸入NULL  
        System.out.println(min(null));  
    }  
}  

運行結(jié)果：

http://wiki.jikexueyuan.com/project/for-offer/images/8.png" alt="" />