旋轉數組的最小數字，旋轉數組數字

旋轉數組的最小數字，旋轉數組數字

旋轉數組的概念：把一個數組最開始的若干個元素搬到數組的末尾，我們稱為數組的旋轉。例如{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int MinNum(int* numbers, int length)
 5  {
 6      if(numbers == NULL || length <= 0)
 7      {
 8          cout<<"invalid input" <<endl;
 9          exit(-1)    ;
10     }
11 
12      int start = 0 ;
13      int end = length - 1;
14      int middle = start;
15 
16      while(numbers[start] >= numbers[end])
17      {
18          if(end -start == 1)
19          {
20              middle = end;
21              break;
22          }
23 
24          middle = (start + end) / 2 ;
25 
26          if(numbers[start] == numbers[end] && numbers[middle] == numbers[start])
27          {
28              int result = numbers[start];
29              for(int i = start + 1; i<= end ; ++i)
30              {
31                  if(numbers[i] < result)
32                      result = numbers[i];
33              }
34              return result;
35          }
36 
37          if(numbers[middle] >= numbers[start])
38              start = middle;
39          else if(numbers[middle] <= numbers[end])
40              end = middle;
41      }
42 
43      return numbers[middle];
44  }
45 
46  int main()
47  {
48      int array[] = {1, 0, 1, 1, 1};
49      int length = sizeof(array)/ sizeof(int);
50 
51      int minNum = MinNum(array, length);
52 
53      cout << "最小的數的值: " << minNum << endl;
54 
55      return 0;
56  }