知识卡片

普通读书笔记卡 · 1292.g.1.b.1.d · 生成模型:未记录

二分查找保持候选区间

理解等级:中级

对按同一比较规则升序排列且可随机访问的数组,维护闭区间 [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

    参考来源

    - 位置:《算法技术手册》第5章《二分查找》(spine1539;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1502.html;u117-ch05-005)。 - 结论依据:117全文和03249完整伪代码实读;溢出处理和重复键为实现补充。 - 原始内容:二分查找 二分查找(图5-2)在预先排好序的集合上表现出了比顺序查找更好的性能。二分查找每次将有序集合折半直到找到待查找元素,或者发现待查找元素不在当前的集合中。 图 5-2 二分查找详解 假设你有一本纽约电话簿,并且需要找到"David Mamet"的电话。如果你使用顺序查找的话,你也许需要花费下 - 位置:《算法技术手册》第5章《输入/输出》(spine1539;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1502.html;u118-ch05-005)。 - 结论依据:118要求集合按键有序;键可比较本身并不意味着数组已排序,查找比较规则也必须与排序规则一致。存在性接口不规定重复键返回哪一个。 - 原始内容:键值的有序。我们也必须能够将这个数据结构分成数个子集进行查找,这样我们就使用了“分治法”来解决这个问题。二分查找的输出是真或者假。 - 位置:《算法技术手册》第5章《使用环境》(spine1540;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1503.html;u119-ch05-005)。 - 结论依据:119的对数结论计数的是比较次数;若访问中点或比较本身不是常数,实际时间需要加上相应成本。 - 原始内容:对数次数的检查。 - 位置:《算法技术手册》第5章《解决方案》(spine1542;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1505.html;u121-ch05-005)。 - 结论依据:121图03250的Java实现以compareTo判断方向;其 (low+high)/2 在大型索引上可能整数溢出,且仅拒绝null目标,集合中null元素能否比较仍需约定。实现Comparable接口本身不能保证调用者正确维护一致的顺序。 - 原始内容:Java代码是操作任何基类T(使用Java的泛型)的二分查找的实现。Java提供了java.util.Comparable接口,这个接口包含一个方法,compareTo。任何正确实现了这个接口的类能够保证其实例的全序。 例5-5:二分查找的Java实现 在这个实现中使用了三个变量:low、high和 - 位置:《算法技术手册》第5章《分析》(spine1544;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1507.html;u123-ch05-005)。 - 结论依据:123的精确比较次数表述漏掉边界:例如 n=1 时最多一次比较,而 log₂1=0。对 n>0,常见闭区间实现最坏次数为 ⌊log₂n⌋+1;03251–03252是内存与磁盘条件下的历史实验,倍率不宜泛化。 - 原始内容:log(n),如果n是2的幂;否则的话,就是log(n)」。如果我们仅仅使用一个操作来决定两个元素是相等,小于或者大于(这个决定也许是有Comparable接口来做出的),那么仅仅需要log(n)」次比较操作,这个算法的性能是O(log n)的。 我们执行了100次实验,每次实验在集合中执行524