题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减序列的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
1 class Solution { 2 public: 3 int minNumberInRotateArray(vector<int> rotateArray) { 4 if(rotateArray.empty()) 5 return 0; 6 int index1 = 0; 7 int index2 = rotateArray.size()-1; 8 int indexMid = index1; 9 while(rotateArray[index1] >= rotateArray[index2]){ 10 // quit condition 11 if(index2 - index1 == 1){ 12 indexMid = index2; 13 break; 14 } 15 indexMid = (index1 + index2) / 2; 16 //the three numbers are equal 17 if(rotateArray[index1] == rotateArray[index2] 18 && rotateArray[indexMid] == rotateArray[index1]){ 19 return MinInOrder(rotateArray,index1,index2); 20 } 21 //no equal 22 if(rotateArray[indexMid] >= rotateArray[index1]){ 23 index1 = indexMid; 24 } 25 else if(rotateArray[indexMid] <= rotateArray[index2]){ 26 index2 = indexMid; 27 } 28 } 29 return rotateArray[indexMid]; 30 } 31 32 int MinInOrder(vector<int> rotateArray,int index1,int index2){ 33 int result = rotateArray[index1]; 34 for(int i=index1+1;i<=index2;i++){ 35 if(result > rotateArray[i]) 36 result = rotateArray[i]; 37 } 38 return result; 39 } 40 };