旋轉數組的最小數字

02-12

旋轉數組的最小數字

把一個數組最開始的若干元素搬到數組的末尾，我們稱為數組旋轉。
輸入一個遞增有序的數組的一個旋轉，輸出數組中的最小元素。

思路：當數組元素不重複的時候，採用2分查找。

1.當mid中間元素大於start開始元素，那麼最小元素在mid之後。

2.當mid中間元素小於end末尾元素，那麼最小元素在mid之前。

3.當end與start相鄰時候，end就是所要查找的最小元素。

當start元素大於end元素時候，不停的執行步驟123。

當start元素小於end元素時候，start元素就是最小元素。

參考代碼：

#include <stdio.h>int getMin(int* arr,int len){int start = 0;int end = len-1;int mid = start;while(arr[start] >= arr[end]){mid = start+(end-start)/2;if(end - start == 1){ mid = end; break;}if(arr[mid] > arr[start]) start = mid;if(arr[mid] < arr[end]) end = mid;}return arr[mid];}int main(){int arr[5]={3,4,5,1,2};int min = getMin(arr,5);printf("%d ",min);return 0;}