最近刷了几道二分法的题，有些感悟：虽然我已经可以“凭感觉”写出代码，但很多时候我写完回头一看，却说不清为什么这么写对，或者说为什么这样就能找到我要的答案。于是我决定整理一下我对“二分法”的理解，尤其是：
什么时候该用二分法？
如何用“目的”来指导写出正确的二分逻辑？
二分查找与找边界、插入位置、上下界的本质关系是什么？
🧠 一、什么时候可以使用二分法？
✅ 1. 明确的单调性
二分法的根本前提是：在一段区间上存在单调性（递增或递减）。这不一定是数组，也可以是函数，比如：
数组中查找：如 [1, 2, 4, 5, 7]，是单调递增；
函数值中查找：比如 f(x) = x² 在 [0, ∞) 上是递增的，所以我们可以用二分来求 √x；
决策问题：例如“在某个速度下能否完成任务”，这种判断函数 check(x) 可能呈现出形如 [False, False, True, True...] 的“单调布尔值区间”。
✅ 2. 我们要找的答案满足“某种边界性质”
典型例子包括：
找一个数值本身；
找某个值第一次/最后一次出现的位置（左边界/右边界）；
找一个满足某条件的“最小可行解”或“最大可行解”。
✍️ 二、怎么用：我总结的三步走法
步骤 1：确定循环不变量和区间定义
最常见的有两种区间写法：
左闭右闭 [left, right]
左闭右开 [left, right)
我自己更习惯用左闭右闭，因为它写起来统一、逻辑明确。
步骤 2：根据目的写出判断条件
关键思想是：
“你想找什么，就根据它的特性写不等式，指导你如何收缩区间。”
举例：
找左边界（lower bound）：
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
即使等于 target，也继续缩右边，逼近最左的一个。
找右边界（upper bound）：
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
即使等于，也继续缩左边，逼近最右的一个。
📌 边界查找的关键：不会在 == target 时停下，而是继续收缩区间。
步骤 3：确定返回值和终止条件
根据你找的是“值”还是“边界”，选择返回：
right：适合找 √x、找最大满足条件的值；
left：适合找最小满足条件的值、插入位置；
mid：适合直接命中的情况（但通常较少直接返回 mid）。
🧩 三、边界查找的抽象总结
🧠 一句话总结我学到的核心：
“二分法不是模板，而是一种寻找单调区间中的临界点/边界/最值的工具，关键在于你能不能用不等式描述目标的位置关系。”
🛠 附：常用二分框架模板
def binary_search(nums, target):
left, right = 0, len(nums) - 1 # 或其他定义
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid # 精确查找
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 或 left / right，看用途
✅ 最后总结：
我曾经只会模仿地套模板，现在我知道：
什么时候能用二分法：只要存在“单调关系”，不一定是数组；
怎么写出有逻辑的二分法：从“目的”出发推导“条件”和“返回值”；
找边界不是花招，而是对“最左/最右满足条件”的精确控制。
写这篇博客是我将“手感”提升为“结构化知识”的一次练习，希望你也能从中获得一点启发。
