6.旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

知识点：

• 二分查找

解题思路：

• 这道题是一道典型的利用二分查找的题
• 我们首先可以模拟看一下有多少种可能，对应的4种判断条件
  • 12345 arr[left] < arr[right],直接返回arr[left]
  • 34512 arr[left] < arr[mid], left = mid + 1;
  • 45123 arr[mid] < arr[right],right = mid;
  • 10111 特殊情况，left++
• 循环完记得返回arr[left]
• 注意：我们最后返回的值为arr[left]，所以记得循环的初始条件不能为等于，不然当推出循环时便违法得到我们想要的值

解题代码：

function minNumberInRotateArray(rotateArray)
{
    // write code here
    if(rotateArray.length === 0) return 0;
    let left = 0;
    let right = rotateArray.length - 1;
    while(left < right) { // 这里不能是等于，如果是等于最后退出时已经不是我们想要的数了
        let mid = (left + right) >> 1;
        if(rotateArray[left] < rotateArray[right]) {
            return rotateArray[left];
        }else if(rotateArray[left] < rotateArray[mid]) {
            left = mid + 1;
        }else if(rotateArray[mid] < rotateArray[right]) {
            right = mid;
        }else {
            left++;
        }
    }
    return rotateArray[left];