剑指 Offer 11. 旋转数组的最小数字

题目

题目来源：力扣（LeetCode）

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

思路分析

通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为 left，右边界为 right，区间的中点为 mid，最小值就在该区间内。我们将中间元素 numbers[mid] 与右边界 numbers[right] 进行比较，可能会有以下的三种情况：

第一种情况是 numbers[mid] < numbers[right]。这说明 numbers[mid] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是 numbers[mid] > numbers[right]这说明 numbers[mid] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

第三种情况是 numbers[mid] == numbers[right]。由于重复元素的存在，我们并不能确定 numbers[mid] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 numbers[right] 是不是最小值，都有一个它的「替代品」numbers[mid]，因此我们可以忽略二分查找区间的右端点。

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
  let left = 0; // 左边界
  let right = numbers.length -1; // 右边界
  while(left < right) {
    // 二分查找，取区间中间值
    // left + right 在left 和 right特别大的时候可能会造成溢出，使用减法避免了溢出发生
    const mid = left + Math.floor((right - left) / 2);
    //情况一： numbers[mid] < numbers[right], 说明中间值 numbers[mid] 是最小值右侧的元素，此时可以忽略二分查找区间的右半部分
    if (numbers[mid] < numbers[right]) {
      // 忽略二分查找区间的右半部分，将右边界置为 mid
      right = mid;
    } 
    //情况二： numbers[mid] > numbers[right], 说明中间值 numbers[mid] 是最小值左侧的元素，此时可以忽略二分查找区间的左半部分
    else if (numbers[mid] > numbers[right]) {
      // 忽略二分查找区间的左半部分，将左边界置为 mid + 1
      left = mid + 1;
    } 
    // 情况三：numbers[mid] == numbers[right]，可能存在重复元素，因此并不能确定中间值 numbers[mid] 是在最小值的左侧还是右侧
    // 由于它们的值相同，所以无论 numbers[right] 是不是最小值，都有它的 替代品 numbers[mid]，因此可以忽略二分查找的右端点
    else {
      // 忽略二分查找的右端点，right 往左移
      right -= 1;
    }
  }
  return numbers[left]
}