算法专题：二分查找

二分查找的核心是单调性和一致的区间语义，而不是背诵某段固定代码。

🧭 什么时候考虑这个专题

任意命中使用普通二分；重复值边界使用 lower/upper bound；可行性存在阈值时对答案空间二分。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点	核心规则	常见复杂度
搜索空间单调性	二分要求判定结果在搜索空间中只发生一次方向变化	通常 O(log R) 次判定
闭区间循环	区间 [left,right] 非空条件是 left <= right	O(log n)
半开区间右边界	区间 [left,right) 可把 right 初始化为 Length	O(log n)
中点溢出	使用 left + (right-left)/2 避免直接相加溢出	每轮 O(1)
下界与上界	下界找第一个 >= target，上界找第一个 > target	O(log n)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

• 搜索空间单调性： 搜索空间不一定是数组，但必须能证明单调阈值
• 闭区间循环： 检查 mid 后必须用 mid-1 或 mid+1 排除它
• 半开区间右边界： 循环和更新必须始终保持右端不包含语义
• 中点溢出： 下标与答案范围仍需选择足够宽的整数类型
• 下界与上界： 不存在符合位置时二者都可能返回 Length

C# 实现检查

1. 方法签名与题目契约一致，不依赖控制台输入输出。
2. 数值计算检查 int 溢出，必要时先提升为 long。
3. 集合选择说明平均复杂度、顺序语义和重复值处理。
4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

• 搜索空间单调性： 不要把“任何整数答案都可以直接二分”当成规则。
• 闭区间循环： 不要把“闭区间中 right 应初始化为 Length”当成规则。
• 半开区间右边界： 不要把“闭区间与半开区间更新规则可以任意混用”当成规则。
• 中点溢出： 不要把“(left+right)/2 在所有范围都安全”当成规则。
• 下界与上界： 不要把“上下界都等价于找到任意一个 target”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。