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

更新時間：2016年03月15日 16:50:04 作者：wuzhekai1985

這篇文章主要介紹了C語言輸出旋轉(zhuǎn)后數(shù)組中的最小數(shù)元素的算法原理與實例,數(shù)組旋轉(zhuǎn)就是把開頭的幾個指定的元素放到數(shù)組的末尾,需要的朋友可以參考下

問題描述：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。
     思路：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，時間復雜度顯然是O(n)。但這個思路沒有利用輸入數(shù)組的特性。既然有時間復雜度更小的算法，我們?nèi)菀紫氲蕉植檎遥驗樗臅r間復雜度為O(logn)。這個問題是否可以運用二分查找呢？答案是肯定的。觀察一下數(shù)組的特性，首先遞增（稱為遞增a），然后突然下降到最小值，然后再遞增（稱為遞增b）。當然還有一種特殊情況，就是數(shù)組遞增，中間沒有下降，即旋轉(zhuǎn)元素個數(shù)為0。
      對于一般的情況，假設A為輸入數(shù)組，left 和 right 為數(shù)組左右邊界的坐標，考察中間位置的值A(chǔ)[mid] ，如果A[mid] <= A[right]，表明處于遞增b，調(diào)整右邊界 right = mid；如果A[mid] >= A[left]，表明處于遞增a，因此調(diào)整左邊界left = mid。當左右邊界相鄰時，較小的一個就是數(shù)組的最小值。其實，對于一般情況，右邊界所指的元素為最小值。
     對于特殊情況，即旋轉(zhuǎn)個數(shù)為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 錯誤

第五組的結(jié)果是錯誤的。其實，上述算法適用于嚴格遞增的數(shù)組，對于非嚴格遞增，用二分法無法保證正確解。有興趣的讀者，可以試試，對于非嚴格遞增的序列，是否可以用二分法得到正確解。
參考代碼：

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

您可能感興趣的文章: