二分查找

May 8, 2015

Categories:
codejam

给定数组nums = [1, 2, 3, 4, 5],

如何求middle的位置正好二分

以0为开始位置对于偶数: len(nums)/2 - 1 (+0.5) 对于奇数: len(nums)/2

因此中心点的位置为: l + (r - l) / 2 靠左， l + (r - l + 1) / 2 靠右，长度length: r-l+1, 边界lr左右包含。

为什么除以 2 会出现"靠左 / 靠右"

因为计算机底层是二进制，整数除法 / 会截断余数（向下取整）。当区间长度 r - l 是奇数时，除以 2 会丢掉的 0.5：

(r - l) / 2：奇数长度被截断 → 落在左边（靠左中间位）
(r - l + 1) / 2：奇数长度先补 1 再除 → 落在右边（靠右中间位）

区间长度为偶数时没有余数，两者结果相同。而二分时"靠左"配合 l = m + 1 / r = m 更新区间，恰好保证不会死循环。

qtopie.github.io

现在加入我们要做数组倒序交换, 我们可以这么做

// Recommended
for i, j := l, r; i < j; i, j := i+1, j-1 {
  nums[i], nums[j] = nums[j], nums[i]
}

// 或者只有r,l之间有2个及以上元素的时候才需要偏移
for k := 0; k < (r-l+1)/2; k++ {
  nums[l+k], nums[r -k] = nums[r -k], nums[l+k]
}

扩展：求第一个大于等于 target 的下标（lower bound）

这道题的完整解法先不讨论，只看其中二分法的应用。

在 300. 最长递增子序列的 O(n log n) 解法中，tails 数组保持单调递增，对每个元素 e，我们都要找到"tails 中第一个 >= e 的位置"并用 e 替换它。这就是 lower bound，只写二分那一部分：

// 在升序数组 nums 中找第一个 >= target 的下标；不存在时返回 len(nums)
func lowerBound(nums []int, target int) int {
	l, r := 0, len(nums) // 左闭右开 [l, r)
	for l < r {
		m := l + (r-l)/2
		if nums[m] >= target {
			r = m // m 可能是答案，保留在区间内
		} else {
			l = m + 1 // m 不可能是答案，排除
		}
	}
	return l // 结束时 l == r，即第一个 >= target 的下标
}

在 LIS 里的用法只是"替换或追加"两行：

p := lowerBound(tails, e)
if p == len(tails) {
	tails = append(tails, e)
} else {
	tails[p] = e
}

同一套模板只改判断条件，就能得到不同变体：

目标	判断条件（满足时 `r = m`，否则 `l = m+1`）	结束返回值
第一个 `>= target`（lower bound）	`nums[m] >= target`	`l`
第一个 `> target`（upper bound）	`nums[m] > target`	`l`
最后一个 `<= target`	等价于 upper bound 的结果 `- 1`	`l - 1`

怎样思考数组下标才不出错

核心一句话：始终维护"答案在 [l, r) 内"的不变量，让区间每一步严格收缩，结束时 l 就是答案。

二分查找本质上是在排序数组上找"否定性质"与"肯定性质"的分界点：

维护不变量：nums[0..l-1] 都不满足条件（否定），nums[r..n-1] 都满足条件（肯定）。
我们要找的是第一个满足条件的位置，它等于收敛后的 l（也是 r）。

按下面几步思考就不会错：

统一用左闭右开 [l, r)：初始化 l = 0, r = len(nums)。这样"找不到"的情况天然返回 len(nums)，无需特判（空数组、全小于 target 都一样）。
循环条件写 l < r：l == r 表示区间为空、分界点已找到，此时 l 和 r 相等，返回谁都一样。
先定移动方向，再写条件：检查 nums[m]——
- 若满足条件：m 本身可能就是答案，必须保留 → r = m
- 若不满足：m 一定不是答案，排除 → l = m + 1
- 每一步要么 r 变小、要么 l 变大，区间严格收缩，因此必然终止、不会死循环。
mid 靠左还是靠右，取决于你是否会写 l = m：
- 标准写法用靠左的 l + (r-l)/2，配合 l = m+1 / r = m，永远不会死循环，所以优先用它。
- 只有当你需要 l = m（例如求"最后一个满足条件的位置"）时，才改用靠右的 l + (r-l+1)/2——否则当 r == l+1 时 m == l，l = m 会让区间卡住。
写完用边界样例自检：对 [1, 2, 3, 4, 5] 分别找 0（应返回 0）、3（应返回 2）、6（应返回 5）；再对长度为 1、2 的数组各验一次，能快速暴露 off-by-one。