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

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]

这种方法很快，但浪费了很多空间。

---

是否有一种通用的数据结构/算法来解决这种问题？

- Lee Chou

---

“Section”号码不能太大，我认为一个简单的数组就可以。 - throwit

你有多少个部分？在运行时是否可能创建/更新/删除部分？ - Толя

我只是以网页上的部分作为例子，但它实际上用于更大的数组，因此一个通用的算法会很好。@Толя 我没有考虑过实时修改它，但如果能有一个良好的复杂度也是很好的。 - Lee Chou

@LeeChou 如果你还有一个更大的情景，并且想要一个通用的解决方案，那么 n-k 树是一个不错的选择；它的插入和搜索复杂度均为 O(lg n)，空间效率为 O(n)。 - Chris K

一个键为连续整数的哈希表没有意义。如果你选择这种方式，只需使用数组，这样查找就不需要对整数进行哈希处理，而且存储密度更高。 - Peter Cordes

Answer 1

我喜欢你的第一个选项，二分搜索非常高效，正如你所说，第二个选项不够节省空间。

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

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

- Chris K

Answer 2

最简单和有效的方法是使用具有O(LogN)复杂度的二分查找。

您的第二个选项具有更好的复杂度O(1)，但在预填充方面存在缺点。对于二分查找，预填充更简单。

如果您不在运行时更新部分，则这两种方法都是最佳选择。

如果您需要在运行时添加/删除/更新部分，则需要数据结构。 因为您的方法需要使用O(N)更新预填充数据。这意味着更新/添加/删除部分操作可能需要O(N)的时间。

- Толя