旋转数组的最小数字

意外发现的小代码：

 char * parr = new char[10];
    memset(parr, 0, 10);
    int len_one = strlen(parr);
    int len_two = sizeof(parr);
    int len_three = sizeof(*parr);
    cout << len_one << " and " << len_two << " and " << len_three << endl;

答案：0,4,1

麻烦的做法：遍历数组，找出最小值

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int length = rotateArray.size();
        if(length == 0)
            return 0;
        int num = 6501;
        for(int i = 0; i < length; i++)
        {
            if(rotateArray[i] < num)
                num = rotateArray[i];
        }
        return num;
    }
};

思路：二分思想

剑指offer做法：正常的二分就是用两个指针，如果mid>=left 那么最小的数在后面，所以是left = mid;如果mid<=right那么最小的数在前面，所以right= mid;

循环条件是什么呢？左边的数字一定大于或等于右边的数字

两种特殊情况：

1.左边的数字小于右边的数字，在旋转0个数的情况下，即为排好序的数组，没旋转

2.left， right， mid 都相等的情况：例如：{0，1,1,1,1} 旋转后：{1,0,1,1,1,} 或者{1,1,1,0,1} ，在相等的情况下，left 和 right 指针就不能按照原来的规则移动了，因为最小的数可能在左边也可能在右边。这种情况只能采取一种办法，就是顺序查找最小的数。

class Solution {
public:
    int minNumber(vector<int> rotateArray,int left,int right)
    {
        int num = rotateArray[left];
        for(int i = left+1; i <= right; i++)
        {
            if(rotateArray[i] < num)
                num = rotateArray[i];
        }
        return num;
    }
int minNumberInRotateArray(vector<int> rotateArray) {
    int length = rotateArray.size();
    if(length == 0)
        return 0;
　　 if(length == 1)
　　　　　　return  rotateArray[0];

int left = 0;
    int right = length - 1;
    int mid = left;//防止旋转后的数组已经排好序,这样left < right
    while(rotateArray[left] >= rotateArray[right])
    {
        if(left + 1 == right)
        {
            mid = right;
            break;
        }
        mid = left + (right - left )/2;
        if(rotateArray[left] == rotateArray[right] && rotateArray[mid] == rotateArray[left])
        {
            //顺序查找
            return minNumber(rotateArray,left,right);
        }
        if(rotateArray[mid] >= rotateArray[left])
            left = mid;
        else if(rotateArray[mid] <= rotateArray[right])
            right = mid;
    }
    return rotateArray[mid];
}
};

测试：

功能测试：数组中可能有重复的数字

边界值测试：1.一个升序数组2.只包含一个数字的数组

特殊输入：输入空