arrays - 二分搜索性能比线性搜索差

Question

我在 leetcode.com 上练习基本的编程技能(我强烈推荐它。它很棒)，我遇到了一个有趣的结果。

我试图找到具有严格升序值的给定数组 A 的第一个不动点。

我用两种方式做到了这一点。一、二分查找/线性时间混合

    start, end = 0, len(A) - 1
    while(start <= end):
        middle = (start + end) / 2
        if A[middle] == middle:
            for i in range(start, middle + 1):
                if A[i] == i:
                    return i
        elif A[middle] > middle:
            end = middle - 1
        elif A[middle] < middle:
            start = middle + 1
    return -1  

这是简单的二分搜索，直到找到匹配项，然后我遍历所有可能的第一个固定点，一个接一个，直到找到第一个匹配项。这就是线性部分的用武之地。例如，假设 len(A) = 1001 和 A[500] = 500 是唯一的固定点，然后我找到它在二进制搜索的一次迭代中，但随后我必须从索引 0 到 500 一个接一个地查找第一个匹配项。那是 n/2 或者换句话说 O(n)

第二种解决方案是纯二分查找

    start, end = 0, len(A) - 1
    fixed_point = -1
    while(start <= end):
        middle = (start + end) / 2
        if A[middle] == middle:
            fixed_point = middle
            end = middle - 1
        elif A[middle] > middle:
            end = middle - 1
        elif A[middle] < middle:
            start = middle + 1
    return fixed_point     

本以为会更好，但实际上更糟。

第一个解决方案在运行时间方面击败了所有提交的 97%，运行时间为 40 毫秒。

第二个解决方案仅击败了所有提交的 72%，运行时间为 48 毫秒。

我很好奇为什么会这样。第二种解决方案真的更好吗？

Answer 1

在if A[middle] == middle:“找到不动点的任意索引”的位置。第一个版本更有效地找到中点运行的开始，假设它发生在“接近”(fsvo)线性扫描的开始:每个二进制循环的成本“更昂贵”(较大的 C)，无论所需的循环数如何(O 复杂性)。 对于特定的退化输入，应该可以构建纯二进制搜索更好的情况:例如。 n 的大小和输入的分布。

例如，[0, 0, 0 ..., midpoint=1, 1, 1 ...] 的退化情况将是 O(n) 在第一个版本中，因为线性循环将超过 start=0..midpoint=n/2¹。 使用这种退化数据和足够大的 n 值，普通二分搜索将占主导地位，因为它的边界更好。但是，假设它是“分布良好的随机数据”，那么线性的方法探针可以在非常小的线性扫描集上磨练(最终循环的 C 较小)。

这类似于为什么线性扫描对于小型数组更快，以及为什么合并排序或快速排序(例如)可能会切换到插入排序以进行近叶排序。 Big-O 将行为描述为 n -> Infinity，而不考虑常数成本。

¹扫描也可以是 midpoint=n/2..start=0.. 在这种情况下，显示的退化情况是理想情况和对应的退化情况将是 [0, 1, 1, 1 ...]。