<span>查找旋转数组的最小值</span>
查找旋转数组的最小值：
假设一个排序数组以某个未知元素为支点做了旋转，找出旋转后数组中的最小值，假定数组中没有重复元素。
如：原数组1，2，3，4，5，6，7旋转后得到4，5，6，7，1，2，3。旋转后的最小值为1。
问题分析：
这里不做过多的介绍，旋转之后的数组实际上可以划分为两个有序的数组，前面子数组的大小大于后面子数组的大小。
最小的元素就是两个数组的分界线。
程序实现：
1 /*************************************** 2 FileName FindMinRotateArray.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/3 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 int FindMinRotateArray(int* A,int size){ 16 int Low = 0; 17 int High = size-1; 18 int mid; 19 while(Low < High){ 20 mid = (Low + High) / 2; 21 if(A[mid] > A[High]){ //最小值在右半部份 22 Low = mid + 1; 23 } 24 else if(A[mid] < A[High]){//最小值在左半部分 25 High = mid; 26 } 27 } 28 return A[Low]; 29 } 30 int main() 31 { 32 int a[] = {4,5,6,7,1,2,3}; 33 int FindMinNum = FindMinRotateArray(a,sizeof(a)/sizeof(int)); 34 cout<<"the FindMinNum: "; 35 cout<<FindMinNum<<endl; 36 return 0; 37 }
运行结果：
转载请注明出处：
C++博客园：godfrey_88
