153. 查找旋转数组的最小值

题目

给定一个从某一位置旋转过的升序数组，查找这个升序数组的最小值。
例如有一个升序数组 [0,1,2,3,4,5,6]，从 4 号位旋转后得到[4,5,6,7,0,1,2]。以 O(logn) 的时间复杂度查找这个数组中的最小值。

解析

二分查找的时间复杂度为 O(logn)。
对于一个旋转后的升序数组来说，假设头位置为 head，尾部为 tail，如果二分取一个中间值 mid，那么有以下几种可能的情况。

(1)
mid > head & mid > tail
说明最小值位于 nums[mid+1:tail]
(2)
mid < head & mid < tail
说明最小值位于 nums[head:mid]
(3)
mid > head & mid < tail
说明最小值就是 nums[head]

伪代码

head = 0
tail  = n

for tail > head
  mid = (head+tail) / 2
  if mid > head & mid > tail
    head = mid+1
    break
  if mid < head & mid <tail
    tail = mid
    break
  return nums[head]
return nums[head]

代码

func findMin(nums []int) int {
    head := 0
    tail := len(nums)-1
    
    for tail > head {
        mid := (head + tail) / 2
        if nums[mid] > nums[tail] {
            head = mid+1
            continue
        }
        if nums[mid] < nums[tail] {
            tail = mid
            continue
        }
    }
    return nums[head]
}

后记

1. 不需要那么麻烦的全部关系判定，只需要找到位于哪一边即可
2. 对于可以从 head 和 tail 判定的问题，因为查找中位数时，在长度为 2 的情况下会查找为首元素，如果和首元素进行判定，不好判定，所以我们和尾元素进行判定，这样能方便的将长度缩减到 1.