程序員經典面試題：數組旋轉算法

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 （如果數組里有重復元素，怎么辦？）
答 案： 2分查找的擴充，考慮 [from,to]這段區間，mid = (from + to) / 2，如果a[mid] < a[to] 則最小值在前半段里，如果a[mid] > a[to], 這段區間發生了跳變，所以最小值在后半段區間里。相等時，當然我們可以比較a[mid]和a[from]，但再相等就沒辦法了。偷懶的做法是直接從前后半 段分別找，然后返回最小的，因此最差時間復雜度是O(n)。當存在相等的數時，可能達到最差時間復雜度。

#include<iostream>

using namespace std;
int a[1000005];
int find(int *a,int from,int to) {
        if (from == to - 1) {
                return (a[from] < a[to])?a[from]:a[to];
        }
        if (from == to) {
                return a[to];
        }
        int mid = (from + to) >> 1,x;
        if (a[mid] < a[to]) {
                x = find(a, from, mid - 1);
                if (x > a[mid]) {
                        x = a[mid];
                }
        }
        else if (a[mid] > a[to]) {
                x = find(a,mid + 1, to);
        }
        else {
                int  x1 = find(a, from, mid - 1);
                int  x2 = find(a, mid + 1, to );
                x = (x1 < x2)?x1:x2;
                if (x > a[mid]) {
                        x = a[mid];
                }
        }
        return x;
}
int main() {
int i,n;
        while (scanf("%d",&n) != EOF) {
                for (i = 0; i < n; ++i) {
                        scanf("%d", a + i);
                }
                printf("%d\n",find(a,0,n -1));
        }
        return 0;
}</pre>