C語(yǔ)言輸出旋轉(zhuǎn)后數(shù)組中的最小數(shù)元素的算法原理與實(shí)例

　　問(wèn)題描述：把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(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。

　　思路：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，時(shí)間復(fù)雜度顯然是O(n)。但這個(gè)思路沒(méi)有利用輸入數(shù)組的特性。既然有時(shí)間復(fù)雜度更小的算法，我們?nèi)菀紫氲蕉�分查找，因�(yàn)樗�的時(shí)間復(fù)雜度為O(logn)。這個(gè)問(wèn)題是否可以運(yùn)用二分查找呢？答案是肯定的。觀察一下數(shù)組的特性，首先遞增（稱(chēng)為遞增a），然后突然下降到最小值，然后再遞增（稱(chēng)為遞增b）。當(dāng)然還有一種特殊情況，就是數(shù)組遞增，中間沒(méi)有下降，即旋轉(zhuǎn)元素個(gè)數(shù)為0。

　　對(duì)于一般的情況，假設(shè)A為輸入數(shù)組，left 和 right 為數(shù)組左右邊界的坐標(biāo)，考察中間位置的值A(chǔ)[mid] ，如果A[mid] <= right="mid；如果A[mid]">= A[left]，表明處于遞增a，因此調(diào)整左邊界left = mid。當(dāng)左右邊界相鄰時(shí)，較小的一個(gè)就是數(shù)組的最小值。其實(shí)，對(duì)于一般情況，右邊界所指的元素為最小值。

　　對(duì)于特殊情況，即旋轉(zhuǎn)個(gè)數(shù)為0。按照上述算法，右邊界會(huì)不斷減少，直到與左邊界相鄰。這時(shí)左邊界所指的元素為最小值。下面給出幾組測(cè)試案例：

　　/pic/pic/pic/pic/pic/p>

　　第五組的結(jié)果是錯(cuò)誤的。其實(shí)，上述算法適用于嚴(yán)格遞增的數(shù)組，對(duì)于非嚴(yán)格遞增，用二分法無(wú)法保證正確解。有興趣的讀者，可以試試，對(duì)于非嚴(yán)格遞增的序列，是否可以用二分法得到正確解。

　　參考代碼：

　　/pic/pic/pic/p>

【C語(yǔ)言輸出旋轉(zhuǎn)后數(shù)組中的最小數(shù)元素的算法原理與實(shí)例】相關(guān)文章：

C語(yǔ)言數(shù)組實(shí)例解析02-21

C語(yǔ)言數(shù)組元素的查詢(xún)11-16

C語(yǔ)言中使用快速排序算法對(duì)元素排序的實(shí)例12-05

C語(yǔ)言冒泡排序算法實(shí)例12-19

對(duì)C語(yǔ)言數(shù)組的總結(jié)以及實(shí)例講解03-13

C語(yǔ)言字符數(shù)組的幾種輸出方式02-10

C語(yǔ)言中實(shí)現(xiàn)KMP算法實(shí)例11-16

關(guān)于c語(yǔ)言約瑟夫問(wèn)題輸出序號(hào)算法12-13

C語(yǔ)言選擇排序算法及實(shí)例代碼03-16