旋转数组的最小数字

function minNumberInRotateArray(rotateArray)
{
    // write code here
    let first = 0;
    let last = rotateArray.length-1;
    while(first<=last){
        if(rotateArray[first]<rotateArray[last]){
            return rotateArray[first];
        }else {
            for(let i = last;i>0;i--){
                if(rotateArray[i]>=rotateArray[i-1]){
                    continue;
                }else{
                    return rotateArray[i];
                }
        }
    }
}
}

function minNumberInRotateArray(rotateArray) {
    // write code here

    //  旋转后是这样子的 - _ - 两边大, 中间小, 一直逼近最中间
    //  直到两个标记位遇见即可
    if (!rotateArray.length) return -1

    let pre = 0, last = rotateArray.length - 1

    while (pre < last) {
        rotateArray[pre] >= rotateArray[last] && pre++
        rotateArray[pre] <= rotateArray[last] && last--
    }
    return rotateArray[pre]
}

虽然是简单题，但有两个坑。

一个是如果 如果mid中间值大于右边界的值的话，mid一定不在左边，且mid一定不可能是最小值，所以 l=mid+1，如果mid中间值小于右边的元素的话，mid可能就是最小值，所以更新r=mid。

二是mid值必须和右边界进行比较，因为和左边界比较时，如果当前区间是有序的，则无法正确的确定最小值在那个区间，比如[8, 1, 2, 3]，第二次比较时，mid值等于2，比左边界1大，但是最小值应该在左边。

function minNumberInRotateArray(rotateArray)
{
    let l=0,r=rotateArray.length-1;
    while(l < r) {
        const mid = l + Math.floor((r-l)/2);
        if (rotateArray[mid] > rotateArray[r]) {
            l = mid+1;
        } else if (rotateArray[mid] < rotateArray[r]){
            r = mid;
        } else {
            --r;
        }
    }
    return rotateArray[l];
}

// 你可以使用O(logN)的时间复杂度通过该题吗?
function minNumberInRotateArray(rotateArray)
{
    // write code here
    // 解法1 暴力法
    // return Math.min(...rotateArray);
    
    // 解法2 二分法
    
    let n = rotateArray.length-1;
    if(n<0) {
        return 0;
    }
    //  二分查找，
    // 要达到二分性质，需要使前半段 nums[i] >= nums[0] 后半段 nums[i]<nums[0]
    // 去除第二段末尾与nums[0]相等的元素
    while(rotateArray[n] == rotateArray[0] && n > 0) {
        n--;
    }
    if(rotateArray[n] >= rotateArray[0]) {
        return rotateArray[0];
    }
    // 开始二分
    let left = 0;
    let right = n;
    while(left < right) {
        let mid = left+right >> 1;
        if(rotateArray[mid] < rotateArray[0]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return rotateArray[right];
}

function minNumberInRotateArray(rotateArray)
{
    if(rotateArray.length==0){
      return 0
    }
    let left=0
    let right=rotateArray.length-1

    while(rotateArray[left]>=rotateArray[right] && left<right){
      let mid=(left+right)>>1
      if(rotateArray[mid]>=rotateArray[left]){
        left=mid+1
      }else{
        right=mid
      }
    }
    return rotateArray[left]
} 

function minNumberInRotateArray(rotateArray)
{
    var length = rotateArray.length;
    var first = 0;
    var target = length - 1;
    var mid = Math.floor((length-1)/2);
    while(first!=target){
        if(rotateArray[mid]<rotateArray[target]){
            target = mid;
            mid = Math.floor((first + target)/2);
        }else if(rotateArray[mid]>rotateArray[target]){
            first = mid + 1;
            mid = Math.floor((first + target)/2);
        }else{
            target = target - 1 ;
            mid = Math.floor((first + target)/2);
        }
    }
    return rotateArray[first];
}

function minNumberInRotateArray(rotateArray)
{
    let len = rotateArray.length
    let left = 0
    let right = len - 1
    let mid
    
    // 边界判断
    if (len == 0) {
        return 0
    }
    
    // 考虑没有旋转的情况
    if (rotateArray[right] > rotateArray[left]) {
        return rotateArray[0]
    }
    
    
    while (left <= right) {
        mid = left + ((right - left) >> 1)
        
        // 如果 mid > mid + 1, 那说明 mid + 1位置就是旋转点
        if (rotateArray[mid] > rotateArray[mid + 1]) {
            return rotateArray[mid + 1]
        }
        
        // 如果 mid < mid - 1, 那说明 mid 位置就是旋转点
        if (rotateArray[mid] < rotateArray[mid - 1]) {
            return rotateArray[mid]
        }
        
        // 因为旋转的一个判定就是第一个元素肯定大于最后一个元素, 所以通过第一个元素就可以移动mid
        if (rotateArray[mid] > rotateArray[0]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
}

function minNumberInRotateArray(rotateArray)
{
    return Math.min(...rotateArray)
    //此处使用的是ES6扩展运算符
    // write code here
}

/**
 * 我的解题思路：
 * 管它是啥数组，反正就是找最小元素呗
 *
 * @param {*} rotateArray 
 */
function minNumberInRotateArray(rotateArray)
{
    // write code here
    return rotateArray.length ? Math.min(...rotateArray) : 0;
}

/**
 * 讨论区TOP1的解题思路：
 * 1.利用二分查找的思路，找到最小中间值
 * 2.考虑mid和right可能的三种情况如下
 * 3.mid > right，那么最小值一定在[mid, right]
 * 4.mid === right，那么需要逐步查找（因为存在[1, 1, 0, 1, 1]这种情况）
 * 5.mid < right，那么最小值一定在[left, mid]
 *
 * @param {*} rotateArray 
 */
function topMinNumberInRotateArray(rotateArray)
{
    // write code here
    let left = 0;
    let right = rotateArray.length - 1;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (rotateArray[mid] > rotateArray[right]) {
            left = mid + 1;
        }
        else if (rotateArray[mid] === rotateArray[right]) {
            right--;
        }
        else {
            right = mid;
        }
    }
    return rotateArray[left];
}