Go猜想录
大道至简,悟者天成
二分法学习的四重境界

摘要

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

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
	}
}

第四境界

在答案集上进行二分

  1. 确定答案范围
  2. 验证答案大小

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 国际许可协议进行许可。