题解 | #旋转数组的最小数字#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */
/*方法1：*/
int minNumberInRotateArray(int* nums, int numsLen ) {
    // write code here
    //直接冒泡排序，取最小；
    for(int i=1;i<numsLen;i++)//最大需要移动numslen-1
    {
        for(int j=0;j<numsLen-i;j++)
        {
            if(nums[j]>nums[j+1])
            {
                int tmp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=tmp;
            }
        }
    }
    return nums[0];
}

/*方法2：*/
int minNumberInRotateArray(int* nums, int numsLen ) {
    //write code here
    /*因为是旋转数组，峰值一定是分界线，mid=(numslen-1)/2,mid+1
    至于如何找到分界线：
    因为从中间值分开，左边的有序序列的所有值都是大于右边的，
    以右边端点为例：
        ==  不可能出现，因为最极端也是右边序列最大=左边序列最小
        mid值>右边  落在左边有序区域----峰值在右恻====mid右移.
        mid值<右边  落在右边有序区域----峰值在左恻====mid左移
    概括来说就是：遇到比右边端点大的右移，遇见比右边小的左移
    */


    int start=0, end=numsLen-1, mid;
  
    while(end-start>=1) {
        mid = (end+start+1)/2;

        if( (nums[mid] < nums[end]))
            end = mid;
        else if( (nums[mid] > nums[end]))
            start = mid;
        else {
            if(nums[start]>=nums[end])
                start++;
            else
                end--;
        } 
    }
    return nums[start];
}