C語言輸出旋轉後數組中的最小數元素的算法原理與實例

問題描述：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個排好序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的.一個旋轉，該數組的最小值為1。

思路：這道題最直觀的解法並不難。從頭到尾遍歷數組一次，就能找出最小的元素，時間複雜度顯然是O(n)。但這個思路沒有利用輸入數組的特性。既然有時間複雜度更小的算法，我們容易想到二分查找，因為它的時間複雜度為O(logn)。這個問題是否可以運用二分查找呢？答案是肯定的。觀察一下數組的特性，首先遞增（稱為遞增a），然後突然下降到最小值，然後再遞增（稱為遞增b）。當然還有一種特殊情況，就是數組遞增，中間沒有下降，即旋轉元素個數為0。

對於一般的情況，假設A為輸入數組，left 和 right 為數組左右邊界的座標，考察中間位置的值A[mid] ，如果A[mid] <= right="mid；如果A[mid]">= A[left]，表明處於遞增a，因此調整左邊界left = mid。當左右邊界相鄰時，較小的一個就是數組的最小值。其實，對於一般情況，右邊界所指的元素為最小值。

對於特殊情況，即旋轉個數為0。按照上述算法，右邊界會不斷減少，直到與左邊界相鄰。這時左邊界所指的元素為最小值。下面給出幾組測試案例：

//{1,2,3,4,5,6,7,8,9,10} 1 //{4,5,6,7,8,9,10,1,2,3} 1 //{1,1,1,1,1,1,1,1,1,1} 1 //{1,9,10,1,1,1,1,1,1,1} 1 //{9,9,9,9,9,9,9,10,1,9} 9 錯誤

第五組的結果是錯誤的。其實，上述算法適用於嚴格遞增的數組，對於非嚴格遞增，用二分法無法保證正確解。有興趣的讀者，可以試試，對於非嚴格遞增的序列，是否可以用二分法得到正確解。

參考代碼：

//函數功能 ： 旋轉數組的最小元素 //函數參數 ： pArray指向數組，len為數組長度 //返回值 ： 最小元素 int FindMin(int *pArray, int len) { if(pArray == NULL || len <= return="" int="" left="" right="" -="" mid="left">>1); if(pArray[right] >= pArray[mid]) right = mid; else if(pArray[left] <= left="mid;" return=""> pArray[left] ? pArray[left]: pArray[right]; }