剑指offer——10旋转数组中最小的数字

 1 class Solution01 {
 2 public:
 3     int minNumberInRotateArray(vector<int> rotateArray) {
 4         if (rotateArray.size() == 0)return 0;
 5         int minN = rotateArray[0];
 6         for (int i = 0; i < rotateArray.size() - 1; ++i)
 7             if (rotateArray[i] > rotateArray[i + 1])
 8                 return minN < rotateArray[i + 1] ? minN : rotateArray[i + 1];
 9         return minN;
10     }
11 };
12 
13 class Solution02 {
14 public:
15     int minNumberInRotateArray(vector<int> rotateArray) {
16         if (rotateArray.size() == 0)return 0;
17         int L = 0, R = (int)rotateArray.size() - 1, M = 0;
18         while (rotateArray[L] >= rotateArray[R])
19         {
20             if (R - L == 1)
21             {
22                 M = R;
23                 break;
24             }
25             M = (L + R) / 2;
26             if (rotateArray[M] == rotateArray[L] && rotateArray[M] == rotateArray[R])
27                 return getMin(rotateArray, L, R);
28             else if (rotateArray[M] >= rotateArray[L])
29                 L = M;
30             else
31                 R = M;
32         }
33         return rotateArray[M];
34     }
35 
36     int getMin(vector<int> Num, int L, int R)
37     {
38         int minN = Num[L];
39         for (; L <= R; ++L)minN = minN < Num[L] ? minN : Num[L];
40         return minN;
41     }
42 };