- 题目描述：
-
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
- 输入：
-
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为一个整数n(1<= n<=1000000)：代表旋转数组的元素个数。
输入的第二行包括n个整数，其中每个整数a的范围是(1<=a<=10000000)。
- 输出：
-
对应每个测试案例，
输出旋转数组中最小的元素。
- 样例输入：
-
53 4 5 1 2
- 样例输出：
-
1 一个修改版的二分查找
1 #include
2 #include 3 using namespace std; 4 5 int a[1000000]; 6 7 int findPos(int a[], int left, int right) 8 { 9 if (left > right)10 return -1;11 12 int mid = left + (right - left) / 2;13 14 if (a[left] < a[mid])15 {16 int pos = findPos(a, mid + 1, right);17 if (pos == -1)18 return left;19 else20 return a[pos] < a[left] ? pos : left;21 }22 else if (a[left] > a[mid])23 {24 int pos = findPos(a, left, mid - 1);25 if (pos == -1)26 return mid;27 else28 return a[pos] < a[mid] ? pos : mid;29 }30 else31 {32 int pos1 = findPos(a, mid + 1, right);33 int pos2 = findPos(a, left , mid - 1);34 35 if (pos1 == -1 && pos2 == -1)36 return mid;37 else if (pos1 == -1)38 return a[mid] < a[pos2] ? mid : pos2;39 else if (pos2 == -1)40 return a[mid] < a[pos1] ? mid : pos1;41 else42 {43 if (a[pos1] < a[pos2])44 return a[mid] < a[pos1] ? mid : pos1;45 else46 return a[mid] < a[pos2] ? mid : pos2;47 }48 }49 }50 51 int main()52 {53 int n;54 while(scanf("%d", &n) != EOF)55 {56 for(int i = 0; i < n; i++)57 scanf("%d", &a[i]);58 59 int pos = findPos(a, 0, n - 1);60 61 cout << a[pos] << endl;62 }63 }