https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
点击查看【bilibili】

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例

  1. 输入：nums = [3,4,5,1,2]
  2. 输出：1
输入：nums = [4,5,6,7,0,1,2]
输出：0

输入：nums = [1]
输出：1

解答

二分法
image.png
1.如果数组长度为1，返回唯一的一个数
2.定义两个指针,第一个left指向数组开头,第二个right指向数组结尾
3.检查数组是否被翻转，如果没有,则返回数组里的第一个数
4.当left小于right时.
取中间作为mid进行二分搜索，如果mid的左边一个数大于mid,
或者mid的右边一个数小于mid，则返回mid
5.否则的话。如果left所在的数小于mid,则将left右移至mid+1位置（砍掉左半边)6.否则的话，将right左移至mid-1位置(砍掉右半边)

答案

var findMin = function(nums) {
  if(nums.length == 1) return nums[0]

  let left = 0, 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[mid] > nums[left]) {
      left = mid + 1
    }else {
      right = mid -1
    }
  }
};