5

我碰巧在 Python 中构建二进制搜索，但这个问题通常与二进制搜索结构有关。

假设我有大约一千个合格的候选人，我正在使用二分搜索进行搜索，采用经典的方法将排序的数据集二等分并重复此过程，以缩小合格的集合以进行迭代。候选人只是一串名字，（first-last 格式，例如“Peter Jackson”）我最初按字母顺序对集合进行排序，然后使用以下方法进行二分：

hi = len(names)
lo = 0
while lo < hi:
  mid = (lo+hi)//2
  midval = names[mid].lower()
  if midval < query.lower():
    lo = mid+1
  elif midval > query.lower():
    hi=mid
  else:
    return midval
return None

此代码改编自此处：https ://stackoverflow.com/a/212413/215608

事情是这样的，上面的过程假设一个完全匹配或根本没有结果。如果查询只是针对“彼得”，但有几个姓氏不同的彼得怎么办？为了归还所有的 Peters，必须确保被平分的“箱子”永远不会变得如此之小，以至于除了符合条件的结果。为了返回所有的彼得，二分过程必须停止并让与正则表达式/常规旧字符串匹配之类的东西。

我不是在问如何实现这一点，而是这种类型的搜索被称为......什么是带有“bin size”分隔标准的二分搜索？有条件地平分数据集的东西，一旦满足条件，就会回退到其他形式的字符串匹配，以确保查询中可以有效地有一个结束通配符（因此搜索“彼得”将得到“彼得杰克逊”和“彼得爱德华兹”）

希望我已经清楚我的意思。我意识到在典型的数据库场景中，名称可能是分开的，这只是作为概念证明。

4

2 回答 2

2

这种两段式搜索我以前没有遇到过，所以不知道它是否有一个众所周知的名字。但是，我可以提出一种方法来执行它。

假设您已经运行了第一阶段并且没有找到匹配项。

您可以使用一对二分搜索和一个特殊的比较器来执行第二阶段。bisect_left二进制搜索将使用与和bisect_right相同的原理。您将无法直接使用这些函数，因为您需要一个特殊的比较器，但您可以将它们用作实现的基础。

现在到比较器。在将列表元素x与搜索键k进行比较时，比较器将只使用x[:len(k)]并忽略其余的x. 因此，在搜索“Peter”时，列表中的所有 Peter 都会比较等于键。因此，bisect_left()tobisect_right()将为您提供包含列表中所有 Peters 的范围。

所有这些都可以通过O(log n)比较来完成。

于 2012-12-17T20:15:08.243 回答
0

在您的二分搜索中，您要么找到完全匹配，要么找到匹配所在的区域。因此，在您的情况下，您需要获取包含和返回所有中间字符串 的区域
的上限和下限（hi lo如您所说） 。Peter

但是，如果您的目标是显示单词的下一个单词，则应该查看 Tries 而不是 BST

于 2012-12-17T20:14:56.647 回答