面试题11. 旋转数组的最小数字

image.png

二分查找

1 有序数组分成了左右2个小的有序数组，而实际上要找的是右边有序数组的最小值
2 如果中间值大于右边的最大值，说明中间值还在左边的小数组里，需要left向右移动
3 如果中间值小于等于当前右边最大值，至少说明了当前右边的right值不是最小值了或者不是唯一的最小值，需要慢慢向左移动一位

  1. package main
  3. import "fmt"
  5. func minArray(numbers []int) int {
  6.     left :=0
  7.     right :=len(numbers)-1
  8.     for left<right{
  9.         mid :=left+(right-left)>>1
  10.         if numbers[mid]>numbers[right]{
  11.             left = mid+1
  12.         }else if numbers[mid]<=numbers[right] {
  13.             right = right-1
  14.         }
  15.     }
  16.     return numbers[left]
  17. }
  19. func main() {
  20.     fmt.Println(minArray([]int{5,1,2,3,4}))//1
  21.     fmt.Println(minArray([]int{3,4,5,6,7,1,2}))//1
  22.     fmt.Println(minArray([]int{2,3,4,5,6,1}))//1
  23.     fmt.Println(minArray([]int{1,3,5}))
  24. }

或者

func minArray(numbers []int) int {
    left :=0
    right :=len(numbers)-1
    for left<=right{
        mid :=left+(right-left)>>1
        if numbers[mid]>numbers[right]{
            left = mid+1
        }else if numbers[mid]<numbers[right] {
            right = mid
        }else{
             right--
        }
    }
    return numbers[left]
}

image.png