知识卡片
二分查找保持候选区间
对按同一比较规则升序排列且可随机访问的数组,维护闭区间 [low,high];比较中点与目标后,匹配则返回,目标较小保留左半区,较大保留右半区,直到 low>high 表示不存在。每次未命中至少排除中点及一侧,最坏 O(log n) 次比较。
避免固定宽整数中 low+high 溢出,可在合适范围约束下使用 low+(high−low)/2。含重复键时普通命中并不保证返回首个或最后一个位置。
118要求集合按键有序;键可比较本身并不意味着数组已排序,查找比较规则也必须与排序规则一致。存在性接口不规定重复键返回哪一个。
119的对数结论计数的是比较次数;若访问中点或比较本身不是常数,实际时间需要加上相应成本。
121图03250的Java实现以compareTo判断方向;其 (low+high)/2 在大型索引上可能整数溢出,且仅拒绝null目标,集合中null元素能否比较仍需约定。实现Comparable接口本身不能保证调用者正确维护一致的顺序。
123的精确比较次数表述漏掉边界:例如 n=1 时最多一次比较,而 log₂1=0。对 n>0,常见闭区间实现最坏次数为 ⌊log₂n⌋+1;03251–03252是内存与磁盘条件下的历史实验,倍率不宜泛化。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 二分查找保持候选区间
- · 输入/输出
- · 使用环境
- · 解决方案
- · 分析
原书出处 · 5 处
- · 查看原书依据
二分查找 二分查找(图5-2)在预先排好序的集合上表现出了比顺序查找更好的性能。二分查找每次将有序集合折半直到找到待查找元素,或者发现待查找元素不在当前的集合中。 图 5-2 二分查找详解 假设你有一本纽约电话簿,并且需要找到"David Mamet"的电话。如果你使用顺序查找的话,你也许需要花费下
- · 查看原书依据
键值的有序。我们也必须能够将这个数据结构分成数个子集进行查找,这样我们就使用了“分治法”来解决这个问题。二分查找的输出是真或者假。
- · 查看原书依据
对数次数的检查。
- · 查看原书依据
Java代码是操作任何基类T(使用Java的泛型)的二分查找的实现。Java提供了java.util.Comparable接口,这个接口包含一个方法,compareTo。任何正确实现了这个接口的类能够保证其实例的全序。 例5-5:二分查找的Java实现 在这个实现中使用了三个变量:low、high和
- · 查看原书依据
log(n),如果n是2的幂;否则的话,就是log(n)」。如果我们仅仅使用一个操作来决定两个元素是相等,小于或者大于(这个决定也许是有Comparable接口来做出的),那么仅仅需要log(n)」次比较操作,这个算法的性能是O(log n)的。 我们执行了100次实验,每次实验在集合中执行524