求旋转数组的最小元素

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

除了正常情况，还要注意考虑三种特殊情况：

(1). 数组是没有发生过旋转的 {1,2,3,4,5,6}

(2). 全相等的数组 {1,1,1,1,1,1}

(3). 大部分都相等的数组 {1,0,1,1,1,1}

 二分查找的思路，最开始  如果数组没有旋转过，直接返回第一个元素，就是最小的元素; 如果旋转过，再按后续

首先获得 mid。 此时 ，若

  (1)  如果 ar[mid] > ar[left], 代表最小值肯定在后半区  left = mid + 1

  (2)  如果 ar[mid] < ar[left], 代表最小值肯定是在前半区到mid之间的（mid也有可能是最小值），  right = mid

  (3)  如果 ar[mid] == ar[left], 这种情况不好说了，需要进一步分析：

                 （1）若 ar[mid] == ar[right] , 最麻烦的情况，前中后都相等，只好排除首尾，继续找   left++   right--

                 （2）若 ar[mid] < ar[right], 代表最小值肯定在前半区， right = mid

                 （3）若 ar[mid] > ar[right], 代表最小值肯定在后半区， left = mid + 1

int xuanzhaunjuzhen(int ar[],int left,int right)
{
    int mid;
    while (left < right)
    {
        if (ar[left] < ar[right])         //代表没有旋转过
            return ar[left];
        mid = (left + right)/2;
        if (ar[mid] > ar[left])         // 最小值在后半区
            left = mid + 1;
        else if (ar[mid] < ar[left])    // 最小值在前半区到mid之间
            right = mid;                 //mid也可能是最小值
        else                        //ar[mid] == ar[left] 
        {
            if (ar[mid] == ar[right])
            {
                ++left;
                --right;
            }
            else if (ar[mid] < ar[right])     //在前半区
                right = mid - 1;
            else           //ar[mid] > ar[right]    在后半区
                left = mid + 1;
        }
    }
    return ar[left];
}