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。當左右邊界相鄰時，較小的一個就是數組的最小值。其實，對于一般情況，右邊界所指的元素為最小值。

【C語言輸出旋轉后數組中的最小數元素的算法原理與實例】相關文章：

C語言數組實例解析10-21

C語言數組元素的查詢08-02

C語言中使用快速排序算法對元素排序的實例06-20

C語言冒泡排序算法實例06-15

對C語言數組的總結以及實例講解09-01

C語言字符數組的幾種輸出方式05-21

C語言中實現KMP算法實例08-09

關于c語言約瑟夫問題輸出序號算法10-16

C語言奇偶排序算法詳解及實例代碼10-30