二分法:旋转数组的最小值、中位数以及搜索旋转数组
本文讲解了旋转数组的最小值、中位数以及搜索旋转数组的最优解以及背后的二分法思想。
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}