编辑代码


// 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
// 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
// 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
// NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

// Solution:https://www.cnblogs.com/edisonchou/p/4746561.html
// - 隐藏条件1:旋转之后的数组实际上可以划分为两个非递减的子数组(记为list-1和list2)
//   - 而且list-1的元素都大于或者等于list-2的元素。
// - 隐藏条件2:最小的元素刚好是这两个子数组的分界线。
// - 隐藏条件3:arr[0]及其之后的若干个元素可能等于arr[length-1],可以在二分前先移动start


function minNumberInRotateArray(arr) {
    // write code here
    if(arr === null || arr.length === 0)
        return 0;
    
    let start = 0;
    let end = arr.length - 1;
    // 一旦发现数组中第一个数字小于最后一个数字,表明该数组是排序的
    // 就可以直接返回第一个数字了
    let mid = start;

    while(arr[start] >= arr[end]) {
        // 退出循环条件
        if(end - start === 1) {
            mid = end;
            break;
        }

        mid = Math.floor((start+end)/2);

        // 特殊情况:如果下标为start、end和mid指向的三个数字相等,则只能顺序查找
        if(arr[start] === arr[mid] && arr[mid] === arr[end]) {
            let min = arr[start];
            for(let i=start+1; i<=end;  i++) {
                if(arr[i] < min)
                    min = arr[i];
            }
            return min;
        }
        // 缩小范围
        if(arr[mid] >= arr[start])       // mid在list-1
            start = mid;
        else if(arr[mid] <= arr[end])    // mid在list-2
            end = mid;
    }

    return arr[mid];
}

// test -------------------------------
let arr = [3, 4, 5, 1, 1, 2];
console.log(minNumberInRotateArray(arr));