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

这道题不能稳定在O(logn)时间复杂度内找到,比如输入给出[2,2,2,...,2,2,2,1,1],这时就必须比较O(n-2)次,这里就不分享我的二分做法了,我分享一个分治思想,每次递归分别求出左右两边的最小值,再从两部分的值之中取一个最小的值.

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */
int minNumberInRotateArray(int* arr, int n ) {
    return n==1?arr[0]:fmin(minNumberInRotateArray(arr,n/2),minNumberInRotateArray(arr+n/2,n+1>>1 ));
}