✅153. 寻找旋转排序数组中的最小值

[bazinga-web]

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

[bazinga-web]

解题思路：

1. 如果数组长度为1，返回唯一的数
2. 定义两个指针分别指向数组的开头及结尾
3. 检查数组是否翻转，如果没有返回最开始的那个数
4. 当left小于right时，取中间作为mid进行二分查找
   当mid右边值小于mid时返回nums[mid+1],
   当mid左边值大于mid时返回nums[mid]
5. 上述两种都不符合时，如果left所在数小于mid所在数，则
   left右移mid+1位置，否则将right左移至mid-1位置

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  if (nums.length < 2) {
    return nums[0];
  }
  let left = 0;
  let right = nums.length - 1;

  if (nums[right] > nums[0]) {
    return nums[0];
  }

  while (left < right) {
    let mid = Math.floor(left + (right - left) / 2);

    if (nums[mid] > nums[mid + 1]) {
      return nums[mid + 1];
    }

    if (nums[mid - 1] > nums[mid]) {
      return nums[mid];
    }

    if (nums[left] < nums[mid]) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
};

[Ray-56]

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
	const len = nums.length;
	if (len == 1) return nums[0];

	let left = 0;
	let right = len - 1;
	// 左边小于右边，表示未旋转，直接将最左返回
	if (nums[left] < nums[right]) return nums[left];

	while (left < right) {
		const mid = Math.floor((left + right) / 2);

		if (nums[mid] > nums[mid + 1]) return nums[mid + 1];

		if (nums[mid] < nums[mid - 1]) return nums[mid];

		if (nums[left] < nums[mid]) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
};