用于节查找的数据结构/算法

Question

在给定每个部分的端点列表的情况下,我应该使用什么样的数据结构/算法来查找当前的部分？

例如,如果我有一个包含章节标题和内容的网页,

• 简介(以100px结尾)
• 第1节(以350px结束)
• 第2节(以700px结束)
• 结论(以1200px结束)
• 评论

我目前处于130px,它应该返回我目前处于"第1部分".

选项1

通过端点数组进行二进制搜索

from bisect import bisect_left

arr = [100, 350, 700, 1200]
pos = bisect_left(arr, 130, 0, arr[-1])

但是,对于每个位置变化,这仍然可能需要O(log n).

选项2

哈希表查找当前位置,

lookup = {0: "Introduction"
          1: "Introduction"
          ...
          10: "Section 1"
          11: "Section 1"
          ...
         }
section = lookup[130/10]

这很快,但浪费了很多空间

---

是否有处理此类问题的通用数据结构/算法？

Answer 1

我喜欢你的第一个选项，二进制搜索对于扫描非常有效，正如你所说，第二个选项空间效率不高。

在计算机图形中缩放的传统且非常通用的解决方案是2d k-tree，它创建一个可以通过坐标查找而不浪费内存的树。具体来说，它的搜索、删除和插入复杂度都是O(log n)，空间复杂度是O(n)。

鉴于您只做一个轴，并且网页往往有 1-100 个部分（并且不太可能有数千个，更不用说数百万或数十亿个部分），那么我个人会考虑使用一个非常简单的数组，然后当有可衡量的好处/需求时，转向更复杂的 k 树。如果您用 C 或其他可以对内存布局进行一定控制的语言编写此代码，那么由于现代 CPU 和内存层次结构（特别是预取器和缓存）的设计，结构数组的扫描速度会异常快。