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

題目描述：

把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾虐秦，我們稱之為數(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谎痢。 NOTE：給出的所有元素都大于0磕昼，若數(shù)組大小為0，請(qǐng)返回0舶得。

題目思考：

首先掰烟，我們看到的非遞減排序數(shù)組，實(shí)質(zhì)上就是一個(gè)遞增數(shù)組，一個(gè)遞增數(shù)組將前面的一部分挪到后面去纫骑，這樣就形成了兩個(gè)遞增的數(shù)組蝎亚，前面一個(gè)數(shù)組中的所有元素都要比后一個(gè)大，那么問題就有了實(shí)質(zhì)的變化先馆，就是求這兩個(gè)數(shù)組的分界線发框，此時(shí)整個(gè)數(shù)組的前一個(gè)元素大于后面一個(gè)元素的時(shí)候我們就可以知道，此時(shí)后面一個(gè)元素就是整個(gè)數(shù)組的最小值煤墙。

題目思路一：

最簡(jiǎn)單最之際的方法梅惯，也是我們最先想到的，但是卻是最不推薦的仿野，直接遍歷比較大小铣减。

題目思路二：

題目思考中的方式，循環(huán)遍歷比較數(shù)組中前后兩個(gè)元素脚作，當(dāng)遇到后一個(gè)比前一個(gè)小的時(shí)候葫哗，將后一個(gè)返回此時(shí)就是最小的元素。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0)
            return 0;
        for(int i = 0; i < rotateArray.size()-1; i++){
            if(rotateArray[i]>rotateArray[i+1]){
                return rotateArray[i+1];
            }
        }
        return rotateArray[0];
    }
};

題目思路三：

此種解法是從二分法出來的球涛，通過二分法不斷逼近最小的值劣针，二分法從時(shí)間復(fù)雜度上來說是O(log(n)),而思路二的時(shí)間復(fù)雜度是O(n)，這種方式來說更加快捷亿扁。

1捺典、先判斷數(shù)組是否為空，為空返回0从祝；
2襟己、我們定義beg、end哄褒、mid三個(gè)指針分別指向數(shù)組的頭稀蟋、尾、中部呐赡；
3退客、判斷數(shù)組是否旋轉(zhuǎn)，就是array[beg]>array[end]链嘀，當(dāng)出現(xiàn)這種狀況的時(shí)候就說明數(shù)組旋轉(zhuǎn)萌狂，沒有的話就說明數(shù)組沒有旋轉(zhuǎn)，此時(shí)我們只輸出array[0]即可怀泊。
4茫藏、當(dāng)array[mid]>=array[beg]的時(shí)候，說明從beg到mid這部分還是遞增的數(shù)組霹琼，那么此時(shí)beg= mid务傲，將數(shù)組的范圍縮小凉当，變成mid～max，繼續(xù)循環(huán)售葡。
5看杭、當(dāng)array[mid]<=array[end]的時(shí)候，說明從mid到end這部分是遞增的數(shù)組挟伙，此時(shí)end = mid楼雹，將數(shù)組的范圍縮小，變成beg～mid尖阔，繼續(xù)循環(huán)贮缅。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0)
            return 0;
        int beg = 0;
        int end = rotateArray.size() - 1;
        int mid =  0;
        while(rotateArray[beg] >= rotateArray [end]){
            
            if((end - beg) == 1){
                mid = end;
                break;
            } 
            mid = (end + beg)/2;
            if(rotateArray[beg] <= rotateArray[mid]){
                beg = mid;
            }
            if(rotateArray[end] >= rotateArray[mid]){
                end = mid;
            }
            
        }
        return rotateArray[mid];
    }
};

此思路存在的容易犯錯(cuò)的地方：因?yàn)閿?shù)組是分成2段的，我們只能知道這兩段的單調(diào)性介却，數(shù)組分成前后兩半段遞增谴供，所以我們只能分別判斷array[beg] 和 array[end]同array[mid]大小比較，這樣我們才能判斷其單調(diào)性筷笨，單調(diào)遞增就是mid這個(gè)值不斷逼近最小值的方法憔鬼。

思路四：

看到題干我們知道數(shù)組書vector龟劲，我們用STL的函數(shù)將數(shù)組排序胃夏，直接輸出array[0]即可。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        sort(rotateArray.begin(),rotateArray.end());
        return rotateArray[0];
    }
};

題目延伸：

給定一個(gè)有序數(shù)組昌跌，如{1,2,3,4,5,6,7,8,9}仰禀，我們將對(duì)這個(gè)數(shù)組進(jìn)行選擇，未知從什么位置旋轉(zhuǎn)蚕愤。下面給出一個(gè)可能的旋轉(zhuǎn)結(jié)果答恶。如{4,5,6,7,8,9,1,2,3}，我們可以理解為它從元素4位置開始旋轉(zhuǎn)萍诱。之后給定一個(gè)指定的數(shù)字n悬嗓，讓我們從{4,5,6,7,8,9,1,2,3}這個(gè)數(shù)組中找出它的位置，要求時(shí)間復(fù)雜度盡可能的低裕坊。

延伸思路一：

從頭開始遍歷數(shù)組比較大小包竹，返回n的位置。

延伸思路二：

使用STL的方法find()

延伸思路三：二分法

我可以使用上面類似的方法：

解題的思路和上面類似籍凝，分段判斷周瞎，然后二分法逼近。

int search(int n,int[] array){
        int low = 0;        
        int high = array.length-1;
        while(low<=high){
            int middle = (low+high)/2;
            if(array[middle]==n) return middle;
            if(array[middle]>array[low]){  //left is order
                if(n<=array[middle]&&n>=array[low]){
                    high = middle-1;
                }else {
                    low = middle+1;
                }
            }else {         
                if(n>=array[middle]&&n<=array[high]){
                    low = middle+1;
                }else {
                    high = middle-1;
                }
            }
        }
        return -1;  
    }