查找旋转数组的最小值：

假设一个排序数组以某个未知元素为支点做了旋转，找出旋转后数组中的最小值，假定数组中没有重复元素。

如：原数组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 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           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<
           
            <
           
          
         
        
       
      
     

运行结果：

转载请注明出处：

C++博客园：godfrey_88