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

题目

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

( 例如，数组 [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

分析

很显然，如果按照传统的遍历然后求最小值，那么时间复杂度将会是O(n)。按照题目的条件--升序排列，那么很容易想到二分法，二分法的时间复杂度是O(logn)。那么问题来了，对于这道题目，该如何使用二分法呢？

// 思路
// step1
3  4  5  1  2
i           j
// step2
3  4  5  1  2
      i     j
// step3
3  4  5  1  2
      i  j
// step4
// when abs(i - j) <= 1 the min value is min(arr[i], [j])

code

function getRotateArrMinValue(arr) {
  if (arr.length <= 1)  return arr

  let start = 0
  let end = arr.length - 1
  let mid = undefined
  while (start < end) {
    mid = parseInt((start + end) / 2)
    arr[mid] > arr[end] ? start = mid : end = mid
    
    if (Math.abs(start - end) <= 1) {
      return Math.min(arr[start], arr[end])
    }
  }
}