algorithm - 二进制字符串搜索 - 最小 bin 宽度？

Question

我碰巧在 Python 中构建二进制搜索，但这个问题更多地与一般的二进制搜索结构有关。

假设我有大约一千个符合条件的候选人，我正在使用二进制搜索进行搜索，采用经典方法将排序的数据集一分为二并重复此过程，以缩小要迭代的合格集合。候选人只是名字的字符串，(从头到尾的格式，例如“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

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

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

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

Answer 1

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

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

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

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

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