JZ-C-08

剑指offer第八题：旋转数组的最小数字
 1 //============================================================================
 2 // Name        : JZ-C-08.cpp
 3 // Author      : Laughing_Lz
 4 // Version     :
 5 // Copyright   : All Right Reserved
 6 // Description : 旋转数组的最小数字：（二分查找）
 7 //============================================================================
 8 
 9 #include <iostream>
10 using namespace std;
11 
12 int MinInArray(int array[], int start, int end) {
13     int middle = (start + end) / 2;
14     while (start < end) {
15         if (array[end] >= array[middle] && array[middle] >= array[start]) {
16             if (array[start] == array[end] && array[end] == array[middle]) { //若这三个值都相同，二分查找失效★
17                 int min = array[start];
18                 for (int i = 0; i <= (end - start); i++) { //只能顺序查找(只可能存在于第一次查找)
19                     if (array[i] < min) {
20                         min = array[i];
21                     }
22                 }
23                 return min; //找到最小值
24                 break; //退出循环
25             } else {//否则序列为有序序列，二分查找同样失效★
26                 int min = array[start];
27                 return min;
28                 break;
29             }
30         } else {
31             if (array[middle] >= array[start]) {
32                 start = middle;
33             }
34             if (array[middle] <= array[end]) {
35                 end = middle;
36             }
37         }
38         middle = (start + end) / 2;
39         if (middle == start) {
40             break;
41         }
42     }
43     if (array[start] < array[end]) {
44         return array[start];
45     } else {
46         return array[end];
47     }
48 }
49 int main() {
50     int array[] = { 5, 6, 1, 2, 3, 4 };
51 //    int array[] = { 5, 6, 1, 1, 1, 1 };
52 //    int array[] = { 1, 0, 1, 1, 1, 1 };
53 //    int array[] = { 1, 1, 1, 1, 0, 1 };
54 //    int array[] = { 3, 3, 3, 1, 2, 3 };
55 //    int array[] = { 1, 2, 6, 6, 6, 6 };
56 //    int array[] = { 1, 2, 3, 4, 5, 6 };
57     int min = MinInArray(array, 0, 5);
58     cout << "旋转数组中最小值为：" << min << endl;
59     return 0;
60 }