面试题8：旋转数组的最小数字

题目链接：http://ac.jobdu.com/problem.php?pid=1386

思路：采用二分查找的思想。

1、我们找到数组的中间元素

2、如果中间元素大于或等于最左端的元素，中间元素就位于前面的递增子序列，最小元素位于中间元素后面，修改最左端元素的位置；

3、如果中间元素小于或等于最右端的元素，中间元素就位于后面的递增子序列，最小元素位于中间元素前面，修改最右端元素的位置。

重复上面的步骤，可知最后最左端的元素为前面递增子序列的最后一个元素，最右端的元素为后面递增子序列的第一个元素。

考虑特殊情况：最左端元素=中间元素=最右端元素，此时是无法判断最小元素与中间元素的相对位置的。

对于特殊情况，我们要遍历一遍序列，当然只需遍历到后面递增子序列。

还有一种情况，开始最左端的元素就小于最右端的元素（没有进过旋转），不知道要不要考虑！！！

其实要考虑也容易，提前预判，初始值设定为0等都可以很好解决。

code:

 1 #include <cstdio>
 2 using namespace std;
 3 const int MAXN = 1000005;
 4 int a[MAXN];
 5 int binarySearch(int n)
 6 {
 7     int lhs = 0;
 8     int rhs = n - 1;
 9     int mid = 0;    // 当数组没有经过旋转，最小元素为最左端元素
10     while (a[lhs] >= a[rhs])
11     {
12         if (lhs + 1 == rhs)    // 找到了前面递增子序列的最后一个元素，和后面递增子序列的第一个元素
13         {
14             mid = rhs;
15             break;
16         }
17 
18         mid = lhs + ((rhs - lhs) >> 1);    // 获得中间元素的位置
19     
20         if (a[mid] == a[lhs] && a[mid] == a[rhs])    // 特判
21         {
22             bool flag = false;    // 是否找到后面递增子序列的第一个元素
23             int min = a[lhs];
24             for (int i = lhs + 1; i <= rhs; ++i)
25             {
26                 if (min > a[i])
27                 {
28                     min = a[i];
29                     mid = i;
30                     flag = true;
31                 }
32                 if (flag) break;
33             }
34             break;
35         }
36 
37         if (a[mid] >= a[lhs]) lhs = mid;    // 修改最左端元素的位置，逼近前面递增子序列的最后一个元素
38         else  rhs = mid;    // 修改最右端元素的位置，逼近后面子序列的第一个元素
39     }
40     return mid;
41 }
42 
43 int main()
44 {
45     int n;
46     while (scanf("%d", &n) != EOF)
47     {
48         for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
49         int k = binarySearch(n);    // 找到最小元素的位置
50         printf("%d
", a[k]);
51     }
52     return 0;