algorithm - 可以搜索具有 2 个属性的对象的数据结构的设计

Question

我正在尝试想出一种方法来设计一个我可以高效地插入、删除和搜索的数据结构。

要注意的是，搜索函数正在获取一个与输入相似的对象，具有 2 个属性，我需要在我的数据集中找到一个对象，这样我的数据集中对象的第一个和第二个都等于或大于搜索功能输入中的那个。

例如，如果我将以下对象作为输入发送:

object[a] = 9; object[b] = 14

那么找到的有效对象可能是:

object[a] = 9; object[b] = 79

但不是:

object[a] = 8; object[b] = 28

有没有办法存储数据，使搜索复杂度优于线性搜索复杂度？

编辑:我忘了包括在我原来的问题中。搜索必须通过 2 个属性的乘积返回数据集中可能最小的对象。

这意味着符合原始条件的对象的 object[a]*object[b] 的值小于数据集中也符合的任何其他对象。

Answer 1

您可能想要使用k-d 树 数据结构，它通常用于索引k 维点。搜索操作与您执行的操作一样，平均需要 O(log n)。