算法基本型——二分
引言
我还记得在高中的时候,有一道数学题是这么说的:在一片森林中,有一只啄木鸟守护着所有树木的健康,但啄木鸟面对一棵树,如何快速找到害虫呢?
我脑海里第一反应:从上啄到下,不就找到害虫了吗?
数学老师似乎看出了我的想法,他说:啄木鸟比同学们聪明些,它先啄树干的中间,观察害虫的活动范围是在上面还是下面,如果是上面,于是它再去啄上面树干的中间。于是啄木鸟每次只需要关注树干的一半,效率大大提升。
当时稚嫩的我并不知道这其中蕴含的精妙算法,只知道题就是这么做的。多年后,当我接触到编程算法,我才意识到,啄木鸟原来也懂二分,万能的造物者啊。
1. 二分
二分是编程算法中最简单的一个算法,它思想十分朴素,就是每次只关注目标的一半,一半又划分为一半,每次都缩小1/2,那么刚好符合对数的形式,因此二分的时间复杂度为O(lgn) < O(n)。二分的使用有一个重要限定,那就是目标数组是有序的。
2. 二分基本型
比如我们需要在数组[2,4,6,8,9,12]中查找6,用二分代码如下:
func search(nums []int, target int) int { l, r := 0, len(nums) for l < r { mid := l + ((r - l) >> 1) // 这里请大家注意,请用这种方式来二分 if nums[mid] == target { return mid } if nums[mid] > target { r = mid } else { l = mid + 1 } } return -1 }
这就是二分的基本型,也称为标准二分。我们来分析一下。l < r ,说明这是左闭右开,左闭右闭可以吗?当然可以,对应代码如下:
func search(nums []int, target int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) // 这里请大家注意,请用这种方式来二分 if nums[mid] == target { return mid } if nums[mid] > target { r = mid - 1 } else { l = mid + 1 } } return -1 }
这同样是标准二分。我们来观察一下对应关系:
左闭右开
变量 | 初始值 | 过程值 | 判断条件 |
---|---|---|---|
l | 0 | mid + 1 | l < r |
r | len(nums) | mid |
左闭右闭
变量 | 初始值 | 过程值 | 判断条件 |
---|---|---|---|
l | 0 | mid + 1 | l <= r |
r | len(nums)-1 | mid - 1 |
聪明的你应该能体悟到这之间的对应关系。那么这就是二分的基本型。请大家记住这两个固定的关系。
二分细节很复杂,哪里-1,哪里+1?细节是魔鬼,但是我们不用去玩弄那些细节,请记住基本型,我们所有的解题都基于基本型。
3. 二分基本型的应用
3.1. 二分找边界
二分更多的应用是用来找边界,题目LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
找左边界:
func findLeftEdge(nums []int, target int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) if nums[mid] == target { r = mid - 1 // 收紧右边界,目标更靠近左边界 } else if nums[mid] < target { l = mid + 1 } else { r = mid - 1 } } // 返回左边界 return l }
查右边界
func findRightEdge(nums []int, target int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) if nums[mid] == target { l = mid + 1 // 收紧左边界,目标更靠近右边界 }else if nums[mid] < target { l = mid + 1 }else { r = mid - 1 } } // 返回右边界 return r }
可以很清楚的看到,我们查询边界没有做很复杂的改动,都是基于我们的基本型来的。所以基本型要牢记于心。该题题解如下:
func searchRange(nums []int, target int) []int { l := findLeftEdge(nums, target) // 越界 或 目标值不存在,直接返回 if l == len(nums) || nums[l] != target { return []int{-1,-1} } r := findRightEdge(nums, target) return []int{l, r} } // 寻找左边界 func findLeftEdge(nums []int, target int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) if nums[mid] == target { r = mid - 1 // 收紧右边界,目标更靠近左边界 }else if nums[mid] < target { l = mid + 1 }else { r = mid - 1 } } // 返回左边界 return l } // 寻找右边界 func findRightEdge(nums []int, target int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) if nums[mid] == target { l = mid + 1 // 收紧左边界,目标更靠近右边界 }else if nums[mid] < target { l = mid + 1 }else { r = mid - 1 } } // 返回右边界 return r }
3.2. 二分找峰值
请看LeetCode 162. 寻找峰值
我这边直接给出题解:
func findPeakElement(nums []int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) // 收紧右边界,目标更靠近左边界 if mid + 1 < len(nums) && nums[mid] == nums[mid+1] { r = mid - 1 // 向右爬坡 } else if mid + 1 < len(nums) && nums[mid] < nums[mid+1] { l = mid + 1 // 向左爬坡 } else { r = mid - 1 } } return l }
可以看到,我们依然是基于二分基本型来解题的。唯一不同的是,我们比较的目标是nums[mid+1],nums[mid] < nums[mid+1]向右爬坡,nums[mid] > nums[mid+1]向左爬坡,这个过程是不是就像爬坡一样。
3.3. 旋转数组
请看LeetCode 153. 寻找旋转排序数组中的最小值
我这边直接给出题解:
func findMin(nums []int) int { l, r := 0, len(nums)-1 for l <= r { mid := l + ((r - l) >> 1) // 收紧右边界,目标更靠近左边界 if nums[mid] == nums[len(nums)-1] { r = mid - 1 // 向左下坡 } else if nums[mid] < nums[len(nums)-1] { r = mid - 1 // 向右爬坡 } else { l = mid + 1 } } return nums[l] }
可以看到,我们还是基于二分基本型来解题的。不同的是,我们比较的目标是nums[len(nums)-1],nums[mid] < nums[len(nums)-1]向左下坡,nums[mid] > nums[len(nums)-1]向右爬坡,这里就是与找峰值的区别所在,就决定了我们的目标是比较nums[len(nums)-1]而不是nums[mid+1]。这个过程大家仔细去分析下程序就明白了。
4. 二分基本型扩展应用
那掌握基本型是不是就完了?不不不。
上面的题目都是直接给我们数组,我们对着数组就是二分。有难度的题目会那么明显让我们看出二分的意图吗?要有那么简单的话,世界就充满爱了。
我们直接上题:LeetCode 剑指 Offer II 073. 狒狒吃香蕉
请大家好好体味一下这道题,然后再来看题解。
func minEatingSpeed(piles []int, h int) int { sort.Ints(piles) l, r := 1, piles[len(piles)-1] for l <= r { mid := l + ((r - l) >> 1) if judge(piles, mid) == h { r = mid - 1 } if judge(piles, mid) > h { l = mid + 1 } else { r = mid - 1 } } return l } func judge(piles []int, mid int) int { res := 0 for i := 0; i < len(piles); i++ { res += piles[i] / mid if piles[i] % mid != 0 { res++ } } return res }
现在大家能明白了吧,我们要二分的数组是[1, piles[len(piles)-1]],它是隐藏的,需要我们自己挖掘。题目往往难点就在这里,需要通过分析题目后找出隐藏目标。
5. 结语
好了,二分基本型就到这里了。