二分法学习的四重境界

摘要

第一重境界写出不会死循环二分法
第二重境界在排序的输入集上进行二分
第三重境界在未排序输入集上进行二分
第四重境界在结果集上进行二分

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 上绝对不可以用
  - 用非递归实现也并不复杂
面试的时候
- 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 国际许可协议进行许可。