同时具有两个中间（两个指针）的二进制搜索

Question

简而言之，我想将我的数组分成三个子数组，而不是两个首先，这样做是否合乎逻辑？并且请帮助我理解并编写此算法]

def contains(elements, value):
left, right = 0, len(elements) - 1

if left <= right:
    middle = (left + right) // 2

    if elements[middle] == value:
        return True

    if elements[middle] < value:
        return contains(elements[middle + 1:], value)
    elif elements[middle] > value:
        return contains(elements[:middle], value)

return False

Answer 1

您确实可以采用二进制搜索将数组分成多个部分，而不只是两个部分。更笼统地说，这是k元搜索的思想：

• 将数组分成大小相等的k个部分。 （对于二进制搜索，这是两半。对于您的搜索，这将是三分之二）

• 选取前（k-1）个部分的最后一个元素用作键。 （对于二进制搜索，请选择上半部分的最后一个元素，即中间元素。对于您的搜索，将是数组中1/3和2/3点处的元素。）

• 根据您的元素与键的比较方式，或者（1）因为找到了要查找的内容而停止搜索，或者（2）递归浏览相应的部分。 （在二进制搜索中，您要么左分支，要么停止，因为中间元素是您想要的元素，或者右分支。在搜索中，您要么（1）发现您的元素是您选择查看的两个元素之一，要么（2）将下降到包含您的元素的三分之一。）

关于这是否是个好主意-这很好可能是个好主意！在k元搜索中，您每次迭代都会将数组缩小k倍，因此该算法的log _k n =（log n）/（log k）迭代大致是这样。每次迭代都查看k-1个键，因此您要进行O（k）工作。这意味着完成的工作是O（（k / log k）n）。选择k = e（即大约2.7182828）时，数量k / log k最小，因此选择k = 2或k = 3是不错的选择。但是，由于处理器缓存的工作方式，我怀疑选择k = 2总体上会更快，因为缓存未命中次数会更少。 （嘿！我们在实践中倾向于使用二进制搜索，因此这可能不是一个坏主意。）

有趣的是，在数据库中广泛使用的B-tree data structure使用类似于此的内容来存储其元素。由于B树的结构方式，B树通常将k选为一个很大的数字，但是在常规数组搜索中，这可能不是一个好主意。

希望这会有所帮助！