把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1 。

1. 暴力查找（Bruteforce Search）：把旋转数组从前到后遍历一遍，其时间复杂度为 O(n)。很明显，这种思想非常直接粗暴，没有用到旋转数组的性质。

2. 二分查找（Binary Search）：每次查找都把旋转数组平均分成两部分，通过比较当前旋转数组两端点和中间点的值，判断最小值在数组的哪一部分，从而达到缩小搜索范围的目的。其中，两端点为当前的旋转数组索引最小和索引最大的元素，中间点为这两部分子数组的连结元素，也可以看做为轴枢点（pivot point），这里取旋转数组的最小索引和最大索引的算术平均值（向下取整）作为索引，其对应的元素作为中间点。具体过程，如图 2.10 所示。

需要注意，当旋转数组的两端点的值都与中间点的值相等时，因为无法判断最小值在哪一部分，因此需要采用顺序查找方法，即暴力查找。其示例如图 2.11 所示。

#include <stdio.h>
#include <exception>
#include <iostream>

// Declare a parameter exception
class ParamException: public std::exception {
    virtual const char* what() const throw()
    {
        return "Error: input parameters exception!";
    }
};

// find minimum in data[staIndex..endIndex]
int findMinInRotatedArray(int data[], int staIndex, int endIndex)
{
    if (staIndex > endIndex || data == NULL)
    {
        throw ParamException();
    }

    int minimum = data[staIndex];

    if (data[staIndex] >= data[endIndex] && staIndex < endIndex - 1)  // 易错点
    {
        // Use Binary Search
        int midIndex = (staIndex + endIndex) / 2;

        if (data[midIndex] > data[staIndex])
            minimum = findMinInRotatedArray(data, midIndex, endIndex);
        else if (data[midIndex] < data[endIndex])
            minimum = findMinInRotatedArray(data, staIndex, midIndex);
        else
        {
            // Find the minimum sequentially
            for (int i = staIndex+1; i <= endIndex; ++i)
                if (minimum > data[i])
                    minimum = data[i];
        }
    }
    else if (staIndex == (endIndex - 1))
    {
        minimum = data[staIndex] > data[endIndex]? data[endIndex]:data[staIndex];
    }

    return minimum;
}

void unitest()
{
    int arr1[] = {3, 4, 5, 1, 2};
    int arr2[] = {1, 0, 1, 1, 1};
    int arr3[] = {1, 1, 1, 0, 1};
    int arr4[] = {1, 2, 3, 4, 5};

    printf("The minimum of the rotated array {3, 4, 5, 1, 2} is %d.\n", findMinInRotatedArray(arr1, 0, 4));
    printf("The minimum of the rotated array {1, 0, 1, 1, 1} is %d.\n", findMinInRotatedArray(arr2, 0, 4));
    printf("The minimum of the rotated array {1, 1, 1, 0, 1} is %d.\n", findMinInRotatedArray(arr3, 0, 4));
    printf("The minimum of the rotated array {1, 2, 3, 4, 5} is %d.\n", findMinInRotatedArray(arr4, 0, 4));

    // Test index parameter exception
    try {
        findMinInRotatedArray(arr3, 5, 4);
    }
    catch(std::exception& e) {
        std::cout << e.what() << std::endl;
    };
}

int main(void)
{
    unitest();

    return 0;
}