含整数但无数组的问题中Binary Search（二分查找）的适用判定方法

我们平时说的「有序数组可以用二分」只是二分查找的一个典型特例，二分的核心并不依赖数组这个存储结构，只要满足以下三个通用条件，哪怕没有数组、只有整数范围也可以用：

三个核心判定条件 #

• 可以抽象出单调的布尔决策函数
  你要能根据题目要求定义一个输入为整数x、输出为是/否的函数f(x)，这个函数的返回值必须具备单调性：所有返回True的x都集中在数轴的某一侧，返回False的都在另一侧，不会出现True和False穿插的情况。
  举个常见例子：求n的平方根整数部分，你可以定义f(x) = x * x <= n，x小于等于目标平方根的时候f(x)全为True，大于的时候全为False，完全符合单调要求。
• 可以明确确定解的上下边界
  你不需要遍历就能确定答案一定落在整数区间[low, high]内，不需要无限制扩大搜索范围。
  比如求「装完所有货物最少需要多少个承重固定的箱子」，很容易确定下界是1，上界是货物总件数（一件货装一个箱子），边界完全明确。
• 决策函数计算成本足够低
  你可以在O(1)或者和区间长度无关的O(k)时间内算出f(x)的结果，不然二分的对数级时间优势就没有意义。

补充说明 #

有序数组的场景刚好契合上面的规则：比如在升序数组里找target，定义f(x) = arr[x] <= target，天然就是单调的，只是刚好数据存储在数组结构里而已。
你也可以用快速方法验证：随便选几个连续的x值代入决策函数，看返回值是不是只会切换一次真假，同时边界好定，基本就可以用二分求解。

内容的提问来源于stack exchange，提问作者ujzwalp