【34】旋轉數組的最小數字

題目：把一個遞增數組的前幾個元素移動到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序數組的旋轉，輸出旋轉數組的最小元素。例如輸入3 4 5 6 7 1 2，則最小元素為1。規定遞增元素是沒有重複元素的。

分析：

1. 最簡單做法是從頭到尾周遊數組，就可以求出最小元素。時間複雜度O(n)，但是這個是最樸素的方法。

2. 根據旋轉數組的性質，旋轉數組滿足“遞增-最小值-遞增”的性質。利用這個性質我們可以比較快速的求出最小元素。例如3 4 5 6 7 - 1 - 2，就是滿足遞增-最小值-遞增

    具體的做法是設定兩個指針p1和p2，初始化分别指向數組的頭和尾，然後比較兩個指針所指的值和兩個指針中間位置的值的關系。mid = (p1+p2) >> 1；

   （1）如果arr[mid] > arr[p2]，說明最小元素在mid之後則p1 = mid

   （2）如果arr[mid]  < arr[p2]，說明最小元素在mid之前則p2 = mid

   （3）如果兩個指針相差為1的時候，最小值即為最小元素

    時間複雜度為O(logn)，因為每次可以跳到中間位置，類似二分搜尋。

3. 舉例旋轉數組3 4 5 6 7 1 2

    第一次p1指向3，p2指向2，mid指向6，發現arr[mid] > arr[p2]說明最小元素在mid之後，則p1 = mid

    第二次p1指向6，p2指向2，mid指向7，發現arr[mid] > arr[p2]說明最小元素在mid之後，則p1 = mid

    第三次p1指向7，p2指向2，mid指向1，發現arr[mid] < arr[p2]說明最小元素在mid之前，則p2 = mid

    第四次p1指向7，p2指向1，此時p1和p2差1，則最小元素為1.

4. 代碼