題目11：旋轉(zhuǎn)數(shù)組的最小數(shù)字

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾， 我們稱之數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)， 輸出旋轉(zhuǎn)數(shù)組的最小元素。

舉例說明

數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。

思路

一. 順序遍歷

首先能想到的就是順序遍歷，數(shù)組中最小的元素即為整個旋轉(zhuǎn)數(shù)組的最小元素，但算法時間復雜度為O(n)

二. 二分

有序數(shù)組的查找大部分離不開二分。

由旋轉(zhuǎn)數(shù)組的特性，因為經(jīng)排序好的數(shù)組旋轉(zhuǎn)得到的，所以由其特性可以知道，除了不旋轉(zhuǎn)的情況（即原數(shù)組），旋轉(zhuǎn)數(shù)組可以劃分為兩個排序的子數(shù)組，前面的子數(shù)組元素均大于后面的子數(shù)組元素，存在分界線，所以可以想到的就是利用二分查找法，實現(xiàn)時間復雜度為O(logn)

步驟

牢記：要求的是如果發(fā)生過旋轉(zhuǎn)，第二個數(shù)組的第一個數(shù)。

1. 設置兩個指針low,high

low指向數(shù)組的開始位置，也就是第一個數(shù)組的開始位置
high指向數(shù)組的終止位置，也就是第二個數(shù)組的結(jié)束位置
Mid在中點

2. 比較mid與low,high位置的數(shù)組值

一直逼近第二個數(shù)組的第一個數(shù)。

mid與low,high初始數(shù)組值關(guān)系

1. 如果中間位置mid的數(shù)大于low指向的數(shù)，則mid在第一個數(shù)組中。故讓low指向mid所指向的數(shù)，low指向的依然是數(shù)組1的數(shù)
2. 如果中間位置mid的數(shù)小于high所指向的位置，則mid在第二個數(shù)組中。故讓high指向mid指向的數(shù)，high指向的依然是數(shù)組2的數(shù)
3. 知道low和high只差1（相鄰），high指針的數(shù)組值就是所求

注意考慮以下幾種情況的處理：

1. 數(shù)組元素為空的情況（返回0）
2. 數(shù)組元素只有一個的情況（返回該元素）
3. 數(shù)組旋轉(zhuǎn)0個元素，也就是沒有旋轉(zhuǎn)的情況，（最后返回mid對應的值，所以初始時令mid=low，遇到該情況while條件不成立，依然返回mid對應的值）
4. 如果mid的數(shù)既等于p1位置數(shù)，又等于p2位置的數(shù)，這時候不能確定移哪個指針，就必須采用順序查找的方法來尋找最小數(shù)
   如，排序數(shù)組為{0,1,1,1,1}，旋轉(zhuǎn)數(shù)組為{1,0,1,1,1}或者{1,1,1,0,1}，當為這兩種情況時，mid=low=high，無法確定最小的元素在左還是在右，所以這個時候就需要采用順序查找的方式。

代碼實現(xiàn)

public class _11 {
    public static int min(int[] arr) {
        if (arr == null||arr.length< 1) {
            throw new RuntimeException("Invalid input.");
        }   
        if ( arr.length ==1) {
            return arr[0];
        }  
        int low = 0;// 開始處理的第一個位置
        int high = arr.length - 1;// 開始處理的最后一個位置
        int mid = low;// 設置初始值 
        // 確保low在前一個排好序的部分，high在排好序的后一個部分
        while (arr[low] >= arr[high]) {//沒中while就返回mid(low)
            if (high - low == 1) {
                return arr[high];
            }
            mid = low + (high - low) / 2;
            // 如果三個數(shù)都相等，則需要進行順序處理，從頭到尾找最小的值
            if (arr[mid] == arr[low] && arr[high] == arr[mid]) {
                return minInorder(arr, low, high);
            }    
            if (arr[mid] >= arr[low]) {// 如果arr[mid]在前一個排好序的部分
                low = mid;
            }
            else if (arr[mid] <= arr[high]) {// 如果arr[mid]在后一個排好序的部分
                high = mid;
            }
        }
        return arr[mid];
    }
 
    private static int minInorder(int[] numbers, int start, int end) {//順序處理
        int result = numbers[start];//想象一個pivot拉低整條線
        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};//1
        System.out.println(min(array1));
        // 有重復數(shù)字，并且重復的數(shù)字剛好的最小的數(shù)字
        int[] array2 = {3, 4, 5, 1, 1, 2};//1
        System.out.println(min(array2));
        // 有重復數(shù)字，但重復的數(shù)字不是第一個數(shù)字和最后一個數(shù)字
        int[] array3 = {3, 4, 5, 1, 2, 2};//1
        System.out.println(min(array3));
        // 有重復的數(shù)字，并且重復的數(shù)字剛好是第一個數(shù)字和最后一個數(shù)字
        int[] array4 = {1, 0, 1, 1, 1};//0
        System.out.println(min(array4));
        // 單調(diào)升序數(shù)組，旋轉(zhuǎn)0個元素，也就是單調(diào)升序數(shù)組本身
        int[] array5 = {1, 2, 3, 4, 5};//1
        System.out.println(min(array5)); 
        // 數(shù)組中只有一個數(shù)字
        int[] array6 = {2};//2
        System.out.println(min(array6));
        // 數(shù)組中數(shù)字都相同
        int[] array7 = {1, 1, 1, 1, 1, 1, 1};//1
        System.out.println(min(array7));
        // 輸入NULL
        System.out.println(min(null));//java.lang.RuntimeException: Invalid input.
    }
}

輸出：

1
1
1
0
1
2
1
Exception in thread "main" java.lang.RuntimeException: Invalid input.