时间戳

首页 > 解决方案 > 指数搜索与二分搜索

algorithm - 指数搜索与二分搜索

问题描述

除空间复杂度外，二分搜索是否以任何方式击败指数搜索？

标签： algorithmsearch

解决方案

这两种算法都在元素的有序列表中搜索一个值，但它们解决的问题不同。指数搜索明确设计用于无界列表，而二进制搜索处理有界列表。

指数搜索背后的想法很简单：搜索一个边界，然后执行二分搜索。

例子

让我们举个例子。A = [1, 3, 7, 8, 10, 11, 12, 15, 19, 21, 22, 23, 29, 31, 37]. 这个列表可以看作是一棵二叉树（虽然不需要构建树）：

             15
        ____/  \____
       /            \
    __8__           _23__
   /     \         /     \
  3      11       21     31
 / \    /  \     /  \   /  \
1   7  10   12  19  22 29  37

二进制搜索

e = 27（例如）的二分搜索将经历以下步骤

b0)T, R分别为树及其根

                 15 (R)
            ____/  \____
           /            \
        __8__           _23__
       /     \         /     \
      3      11       21     31
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

b1)e比较R：e > 15。分别T, R为T右子树及其根

                 15
            ____/  \____
           /            \
        __8__           _23_(R)
       /     \         /     \
      3      11       21     31
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

b2)e比较R：e > 23。分别T, R为T右子树及其根

                 15
            ____/  \____
           /            \
        __8__           _23__
       /     \         /     \
      3      11       21     31 (R)
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

b3)e比较R：e < 31。分别设T, R为T左子树及其根

                 15
            ____/  \____
           /            \
        __8__           _23__
       /     \         /     \
      3      11       21     31___
     / \    /  \     /  \   /     \
    1   7  10   12  19  22 29 (R)  37

b4) 比较e: R:e <> 29元素不在列表中，因为T没有子树。

指数搜索

e = 27（例如）的指数搜索将经历以下步骤

让T, R分别是最左边的子树（即叶子1）和它的根（1）

                 15
            ____/  \____
           /            \
        __8__           _23__
       /     \         /     \
      3      11       21     31
     / \    /  \     /  \   /  \
(R) 1   7  10   12  19  22 29  37

e1)e比较R：e > 1。让我们R成为树的父节点R并T成为树R的根

                 15
            ____/  \____
           /            \
        __8__           _23__
       /     \         /     \
  (R) 3      11       21     31 (R)
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

e2)e比较R：e > 3。让我们R成为树的父节点R并T成为以根为根的树R：

                 15
            ____/  \____
           /            \
      (R)_8__           _23__
       /     \         /     \
      3      11       21     31 (R)
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

e3)e比较R：e > 8。让我们R成为树的父节点R并T成为以根为根的树R：

             (R) 15
            ____/  \____
           /            \
        __8__           _23__
       /     \         /     \
      3      11       21     31 (R)
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

e4)e比较R：e > 15。R没有父母。设T为 的右子树T并R为其根：

                 15
            ____/  \____
           /            \
        __8__           _23_(R)
       /     \         /     \
      3      11       21     31
     / \    /  \     /  \   /  \
    1   7  10   12  19  22 29  37

e5..7) 见步骤 b2..4)

时间复杂度

为了演示，设N = 2^n为 的大小，A让索引从 开始1。如果N不是 2 的幂，结果几乎是一样的。

让(let )0 <= i <= n成为最小值。请注意，如果您有重复的值，这种间隔可能不是唯一的，因此是“最小值”。A[2^(i-1)] < e <= A[2^i]A[2^-1] = -inf

指数搜索

您需要i + 1迭代才能找到i. （在示例中，您反复从子级跳转到父级，直到找到大于e或没有父级的父级）

然后在选定的时间间隔上使用二进制搜索。这个区间的大小是2^i - 2^(i-1) = 2^(i-1)。

在大小数组中进行二进制搜索的成本2^k是可变的：您可能会在第一次迭代或k迭代后找到值（根据元素的分布进行复杂的分析，但基本上，它在迭代之间1，k你可以事先不知道）

让j_i, 1 <= j_i <= i - 1我们的例子中二分搜索所需的迭代次数（这个间隔的大小是2^(i-1)）。

二进制搜索

让i是最小值，这样A[2^(i-1)] < e <= A[2^i]。因为假设N = 2^n，二分查找会满足这个区间：

我们从根开始A[2^(n-1)]。如果e > A[2^(n-1)]，i = n因为R = A[2^(n-1)] < e < A[2^n]。否则，我们有e <= A[2^(n-1)]. 如果e > A[2^(n-2)], 那么i = n-1, 否则我们继续直到找到i.

您需要使用二进制搜索n - i + 1进行查找的步骤：i

  • 如果i = n，你在第一次迭代时就知道了 ( e > R) 否则，你选择左子树
  • 如果i = n-1，则需要两次迭代
  • 依此类推：如果i = 0，您将需要n迭代。

然后，您将需要j_i如上所示的迭代来完成搜索。

比较

如您所见，j_i迭代对两种算法都是通用的。问题是：是i + 1 < n - i + 1吗？即是i < n - i或2i < n？如果是，则指数搜索将比二分搜索更快。如果否，二分查找将比指数查找快（或同样快）

让我们取得一些距离：2i < n相当于(2^i)^2 < 2^nor 2^i < sqrt(2^n)。而2^i < sqrt(N)，指数搜索更快。只要2^i > sqrt(N)，二分查找就更快。请记住， 的索引e低于或等于2^i因为e <= A[2^i]。

简单来说，如果你有N元素并且如果e在第一个sqrt(N)元素中，那么指数搜索会更快，否则二进制搜索会更快。

这取决于分布，但是N - sqrt(N) > sqrt(N)如果N > 4，则二进制搜索可能比指数搜索更快，除非您知道该元素将在第一个元素中或列表非常短。

如果2^n < N < 2^(n+1)

我不会详细介绍，但这不会改变一般结论。

如果该值超过 2 的最后一次幂，则指数查找边界的成本已经n+2大于二分查找（小于或等于2^(n+1)）。然后你有一个二分搜索要执行，也许在一个很小的时间间隔内，但二分搜索已经是赢家了。

否则，您将值添加A[N]到列表中，直到您获得2^(n+1)价值为止。这不会改变指数搜索的任何内容，并且会减慢二进制搜索的速度。e但是，如果不在第一个sqrt(2^(n+1))值中，这种缓慢的二进制搜索仍然会更快。

空间复杂度

这是一个我不谈论的有趣问题，指针的大小等等。如果您正在执行指数搜索并在元素到达时使用它们（想象时间戳），您不需要一次存储整个列表。您只需要存储一个元素（第一个），然后是一个元素（第二个），然后是两个元素（第三个和第四个），然后是四个元素，......然后是2^(i-1)元素。如果i它很小，那么您不需要像在常规二进制搜索中那样存储大列表。

执行

实施在这里真的不是问题。有关信息，请参阅 Wikipedia 页面：二分搜索算法和指数搜索。

应用程序以及如何在两者之间进行选择

仅当序列无界或您知道该值可能在第一个值中时才使用指数搜索。无界：我喜欢时间戳的例子：它们在严格增长。您可以想象一个存储了时间戳的服务器。您可以询问n 时间戳，并且您正在寻找特定的时间戳。询问 1，然后 2，然后 4，然后 8，...时间戳，并在一个时间戳超过您要查找的值时执行二进制搜索。

在其他情况下，使用二进制搜索。

备注：指数搜索第一部分背后的想法有一些应用：

  • 上限无界时猜一个整数：尝试 1,2,4,8,16,... 超过数字时缩小猜测范围（这是指数搜索）；
  • 在大雾天找一座桥过河：向左走 100 步。如果没找到桥，就回到起点，向右走200步。如果还是没找到桥，就回到初始点，左走400步。重复直到找到桥（或游泳）；
  • 在TCP 慢启动中计算拥塞窗口：将发送的数据量加倍，直到出现拥塞。TCP 拥塞算法通常更加谨慎，并在算法的第二部分执行类似于线性搜索的操作，因为在这里超出尝试会产生成本。

推荐阅读