二分法学习的四重境界
摘要
- 第一重境界写出不会死循环二分法
- 第二重境界在排序的输入集上进行二分
- 第三重境界在未排序输入集上进行二分
- 第四重境界在结果集上进行二分
Outline
- 第一境界
- 写出不会死循环的二分法
- 递归与非递归的权衡
- 二分的三大痛点
- 通用的二分模板
- 第二境界
- 在排序的数据集上进行二分
- 找到满定某个条件的第一个位置或者最后一个位置
- 第三境界
- 在未排序的数据集上进行二分
- 保留有解的一半,或者去掉无解的一半
- 第四境界
- 在答案集上进行二分
- 二分答案并验证答案偏大还是偏小
常见的面试时间复杂度和对应的算法
- O (logn) 二分法比较多
- O (√n) 分解质因数 (极少)
- O (n) 双指针,单调栈,枚举法
- O (nlogn) 排序, O (nlogn 的数据结构上的操作)
- O (n^2), O (n^3),动态规划等
- O (2^n) 组合类的搜索问题
- O (n!) 排列类的搜索问题
独孤九剑 —— 破刀式
根据时间复杂度倒推算法是面试常用策略
如:比 O (n) 更优的时间复杂度只能是 O (logn) 的二分法
Recursion or Non-Recursion (Iteration)
- 两种情况
- 可以使用 Recursion 的几个情况
- 面试官要求你使用 Recursion
- 递归深度不太深,不会造成 Stack Overflow
- 用非递归实现代码写不出写不完
- 不能使用 Recursion 的几个情况
- 面试官要求你使用 Non-recursion
- 递归深度很深,造成 Stack Overflow
- 如 LinkedList 上绝对不可以用
- 用非递归实现也并不复杂
- 可以使用 Recursion 的几个情况
- 面试的时候
- DFS 一般会要求 Recursion 实现
- 二叉树中序遍历的 DFS 要求用 Non-recursion
- 其他算法一般要求 Non-recursion 实现
第一境界
写出不会死循环的二分法
- start + 1 < end
- start + (end - start) / 2
- A[mid] ==, <, >
- A[start] A[end] ? Target
14 · 二分查找
func BinarySearch(nums []int, target int) int {
start, end := 0, len(nums) - 1
for start+1 < end {
mid := start + (end-start)/2
if nums[mid] == target {
end = mid
} else if nums[mid] < target {
start = mid
} else {
end = mid
}
}
if nums[start] == target {
return start
}
if nums[end] == target {
return end
}
return -1
}
死循环的发生
Last Position of Target Nums = [1,1], target = 1 使用 start < end 无论如何都会出现死循环
447 · 在大数组中查找
- 二分
- 指数退避 Exponential Backoff
第二境界
OOXX 在排序的数据集上进行二分
一般会给你一个数组
让你找数组中第一个/最后一个满足某个条件的位置
OOOOOOO… OOXX…. XXXXXX
460 · 在排序数组中找最接近的 K 个数
找到最后一个 < target 的位置,然后从这个位置开始用两根指针向两边走来获得最后最接近的 k 个整数。
时间复杂度 O (logn+k)
func KClosestNumbers(a []int, target int, k int) []int {
left := findLowerClosest(a, target)
right := left + 1
res := make([]int, k)
for i := 0; i < k; i++ {
if isLeftCloser(a, target, left, right) {
res[i] = a[left]
left--
} else {
res[i] = a[right]
right++
}
}
return res
}
func isLeftCloser(a []int, target int, left, right int) bool {
if left < 0 {
return false
}
if right >= len(a) {
return true
}
if target-a[left] != a[right]-target {
return target-a[left] < a[right]-target
}
return true
}
func findLowerClosest(a []int, target int) int {
start, end := 0, len(a)-1
for start+1 < end {
mid := start + (end-start)/2
if a[mid] < target {
start = mid
} else {
end = mid
}
}
if a[end] < target {
return end
}
if a[start] < target {
return start
}
return -1
}
585 · 山脉序列中的最大值
在先增后减的序列中找最大值
二分法,判断山脉趋势,按照取数递归左边或者右边即可。山顶的条件是第一个使得 nums[i] > nums[i + 1] 的 i。当然也可以反过来,最后一个使得 nums[i] > nums[i - 1] 的 i
func MountainSequence(nums []int) int {
start, end := 0, len(nums)-1
for start+1 < end {
mid := start + (end-start)/2
if nums[mid] < nums[mid+1] {
start = mid
} else {
end = mid
}
}
if nums[start] < nums[end] {
return nums[end]
}
return nums[start]
}
159 · 寻找旋转排序数组中的最小值
建立 OOXX 模型
将左半边有序数组看做 O, 将右半边有序数组看做 X
可以把最后一个数当成 target,找最后一个小于等于 target 的位置
func FindMin(nums []int) int {
start, end := 0, len(nums)-1
for start+1 < end {
mid := start + (end-start)/2
if nums[mid] > nums[end] {
start = mid
} else {
end = mid
}
}
min := nums[start]
if nums[end] < min {
min = nums[end]
}
return min
}
62 · 搜索旋转排序数组
方法 1:实现简单
做两次二分,第一次找到最小值,然后在最小值左侧或者右侧去找 target
方法 2:加大难度
在一个 Rotated Sorted Array 上切一刀,可以判断出这一刀切在左半部分还是右半部分,这一刀的两边仍然是 Rotated Sorted Array
func Search(a []int, target int) int {
if len(a) == 0 {
return -1
}
start, end := 0, len(a)-1
for start+1 < end {
mid := start + (end-start)/2
if a[mid] >= a[0] {
if target >= a[0] && target <= a[mid] {
end = mid
} else {
start = mid
}
} else {
if target >= a[mid] && target <= a[end] {
start = mid
} else {
end = mid
}
}
}
if a[start] == target {
return start
}
if a[end] == target {
return end
}
return -1
}
第三境界
在未排序的数据集上进行二分
并无法找到一个条件,形成 XXOO 的模型
但可以根据判断,保留下有解的那一半或者去掉无解的一半
75 · 寻找峰值
如果求的是最高峰或所有峰,复杂度都不可能低于 O (n)
- 上升区间右侧必有峰
- 下降区间左侧必有峰
- 谷的两边都有峰
func FindPeak(a []int) int {
start, end := 1, len(a)-2
for start+1 < end {
mid := start + (end-start)/2
if a[mid] < a[mid-1] {
end = mid
} else if a[mid] < a[mid+1] {
start = mid
} else {
return mid
}
}
if a[start] < a[end] {
return end
} else {
return start
}
}
第四境界
在答案集上进行二分
- 确定答案范围
- 验证答案大小
183 · 木材加工
将一些原木切成 k 段等长小木头,求小木头最长是多少
为什么可以二分?
- 如果能切出 k 段长度为 length 的小木头,一定能切出 k 段更短的小木头
- 如果切不出 k 段长度为 length 的小木头,一定切不出 k 段更长的小木头
- 小木头的长度不可能比最长原木更长
- 小木头的长度不可能比所有原木总和除 k 更长
func WoodCut(l []int, k int) int {
if len(l) == 0 {
return 0
}
sort.Ints(l)
start, end := 1, l[len(l)-1]
for start+1 < end {
mid := start + (end-start)/2
if getPieces(l, mid) >= k {
start = mid
} else {
end = mid
}
}
if getPieces(l, end) >= k {
return end
}
if getPieces(l, start) >= k {
return start
}
return 0
}
func getPieces(l []int, length int) int {
var pieces int
for _, v := range l {
pieces += v / length
}
return pieces
}
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。