二分法:旋转数组的最小值、中位数以及搜索旋转数组

本文讲解了旋转数组的最小值、中位数以及搜索旋转数组的最优解以及背后的二分法思想。


1. 旋转数组的最小值

示例1:

1输入:nums = [3,4,5,1,2]
2输出:1

解法:

 1func findMin(nums []int)int{
 2  var left = 0
 3  var right = len(nums) -1
 4  for;left < right; {
 5    var mid = left + math.Floor((right - left)/2)
 6    if nums[mid] > nums[right]{
 7      // 中间数字大于右边数字,比如[3,4,5,1,2],则左侧是有序上升的,最小值在右侧
 8      left = mid + 1    
 9    } else {
10      // 中间数字小于等于右边数字,比如[6,7,1,2,3,4,5],则右侧是有序上升的,最小值在左侧
11      right = mid
12    }
13  }
14  return nums[left]
15}

如果数组内有重复的元素,这时候再找旋转数组里面的最小值又需要哪些改变呢?

示例2:

1输入: [2,2,2,0,1]
2输出: 0

分析:

  • 这道题相当与上一道题难度是可能存在重复元素,那么 right 指针不能直接移到 mid 位置,因为有可能下一次取 mid 值遗漏掉最小值
  • 如果中间元素=区间尾元素,right 减一
 1func findMin(nums []int)int{
 2  var left = 0
 3  var right = len(nums) - 1
 4  for ;left < right; {
 5    var mid = left + math.Floor((right - left)/2)
 6    if nums[mid] > nums[right]{
 7      // 中间数字大于右边数字,比如[3,4,5,1,2],则左侧是有序上升的,最小值在右侧
 8      left = mid + 1
 9    } else if nums[mid] < nums[right]{
10      // 中间数字小于右边数字,比如[6,7,1,2,3,4,5],则右侧是有序上升的,最小值在左侧
11      right = mid
12    } else {
13      // 中间数字等于右边数字,比如[2,3,1,1,1]或者[4,1,2,3,3,3,3]
14      // 则重复数字可能为最小值,也可能最小值在重复值的左侧
15      // 所以将right左移一位
16      right -= 1
17     }
18  }
19  return nums[left]
20}

2. 旋转数组的中位数

示例1:

1输入:nums = [3,4,5,1,2]
2输出:3

思路:我们只需要找到最小值的下标,再根据下标和数组的 length 求中位数的下标。

解法:

 1func findMedium(nums []int)float64{
 2  var left = 0
 3  var right = len(nums) - 1
 4  for left < right {
 5    var mid = left + int(math.Floor(float64(right-left)/2))
 6    if nums[mid] > nums[right] {
 7      // 中间数字大于右边数字,比如[3,4,5,1,2],则左侧是有序上升的,最小值在右侧
 8	  left = mid + 1
 9    } else if nums[mid] < nums[right] {
10      // 中间数字小于右边数字,比如[6,7,1,2,3,4,5],则右侧是有序上升的,最小值在左侧
11	  right = mid
12    } else {
13      // 中间数字等于右边数字,比如[2,3,1,1,1]或者[4,1,2,3,3,3,3]
14      // 则重复数字可能为最小值,也可能最小值在重复值的左侧
15      // 所以将right左移一位
16	  right -= 1
17    }
18  }
19
20  // 寻找中位数
21  var minIndex = left
22  var midIndex = int(math.Floor(float64(len(nums)) / 2))
23  if len(nums)%2 == 1 {
24    if minIndex < midIndex {
25      var medium = float64(nums[minIndex+midIndex])
26      return medium
27  } else {
28      var medium = float64(nums[minIndex+midIndex-len(nums)])
29      return medium
30    }
31  } else {
32    if minIndex < midIndex {
33      var medium = float64(nums[minIndex+midIndex]+nums[minIndex+midIndex-1]) / 2
34      return medium
35    } else {
36      var medium = float64(nums[minIndex+midIndex-len(nums)]+nums[minIndex+midIndex-len(nums)-1]) / 2
37      return medium
38    }
39  }
40}

翻译: