如何通过二分查找搜索在区块链上根据时间戳定位区块?

阅读 桌面完整版

前两天，我想查一下自己在 STEEM 区块链上一些重要记录对应的区块号，比如：

• 注册了我的账号 #4253590
• 成为见证人 #20190755
• 挖到我的第一个区块 #20390040
• 被孙宇晨大佬代理了 SP #41676911
• 收到一笔 DAO 收入 #95403889

当时手头只有时间戳，却不知道对应的是哪个区块，于是我想到可以用二分查找（binary search）算法来定位。

其实，这个思路在其它区块链上同样适用，并不依赖于特定的链（如 Steem、以太网/Ethereum、比特币/Bitcoin 等）。虽然具体的实现细节（RPC 方法名、时间戳格式等）会有所不同，但整体逻辑是一致的：通过 RPC API 获取某个区块的时间戳；获取最新区块作为上界；然后在区间内使用二分查找。通过多次查询区块时间戳，就能把给定的时间戳映射到最接近的区块号，算法复杂度约为 O(log N)。

当然，大多数区块链也会提供专门的 API 服务，可以直接通过时间返回区块号。我自己就跑过几个程序，从创世区块开始依次获取数据并写入数据库，这样查询时只需要查数据库就能立即得到结果。

可以使用二分搜索算法的场景

在一个搜索空间里，如果自变量 x 随着变化而单调递增或单调递减，那么函数值 f(x) 也会呈现出规律性的单调变化。这种情况下，就可以使用二分搜索算法来快速定位目标值或满足条件的区间。

二分搜索常见的应用场景包括：

• 在区块链上通过时间戳查找区块号（时间戳随区块号递增）。
• 在有序数组中查找目标值或边界。
• 在单调函数（如计算成本函数、概率函数）中寻找满足条件的阈值。
• 在优化问题中缩小答案区间，比如最小化某个代价函数。

总结来说，只要问题满足单调性，二分搜索就能在 O(log N) 的时间复杂度下快速求解，比线性扫描高效得多。

思路概述

1. 通过 RPC 获取某个区块号的时间戳（或用索引器 API 直接查询）。
2. 查询最新区块，作为二分查找的上边界。
3. 在区间 [1, latest_block] 中做二分查找，比较中点区块的时间戳与目标时间戳，收窄区间直到找到最接近（或精确匹配）的区块号。

示例 Python 通用框架

下面给出一个通用的 Python 框架。实际使用时，请把 rpc_call 部分换成目标链对应的 RPC 方法或索引器 API 调用。

def rpc_call(method, params):
    """
    通用 RPC 调用函数示例。
    根据你使用的链替换为 requests.post(...) 并解析返回。
    """
    pass

def get_timestamp_from_block(block_num):
    """
    返回给定区块号的时间戳（Unix 秒或 ISO8601 字符串），取决于链的返回格式。
    需要把链的时间格式统一成可比较的 datetime / timestamp。
    """
    # 示例（伪代码）：
    # resp = rpc_call("get_block", [block_num])
    # ts = parse_timestamp(resp["timestamp"])
    # return ts
    pass

def get_latest_block_and_timestamp():
    """
    返回最新区块号和对应的时间戳，例如 (latest_block, latest_ts)
    不同链可能有不同的 RPC 方法，如 get_block_count / get_chain_head / eth_blockNumber + eth_getBlockByNumber 等。
    """
    pass

def get_block_from_timestamp(target_ts):
    """
    在 [1, latest_block] 区间内使用二分查找定位与 target_ts 最接近的区块号。
    返回找到的区块号（若需要，可返回左右两个候选块以便进一步选择）。
    """
    latest_block, latest_ts = get_latest_block_and_timestamp()

    left, right = 1, latest_block
    result = None

    while left <= right:
        mid = (left + right) // 2
        mid_ts = get_timestamp_from_block(mid)

        if mid_ts < target_ts:
            left = mid + 1
            result = mid
        elif mid_ts > target_ts:
            right = mid - 1
        else:
            return mid  # 精确匹配

    # 返回 result（它表示最后一个 timestamp < target_ts 的区块）
    # 视需求，你可能还要检查 result+1 是否更接近 target_ts
    return result

如何通过二分查找算法根据时间戳获取区块？

按STEEM区块链来举例。

获取区块的时间戳

通过调用 `steemd` 或其它区块链 API，我们可以轻松获取任意区块对应的时间戳。

找到最新区块

这一步为二分查找提供了一个上界。

对目标时间戳进行二分查找

与其线性扫描区块（会非常慢），不如在每一步将搜索区间减半。这样可以将复杂度降低到大约 `O(log N)`，其中 `N` 是当前区块高度。这正是二分查找的魅力——它被认为是迄今为止人类发明的十大算法之一。

为什么这很重要？

如果你想把真实世界的事件（带有时间戳）映射到对应的区块号，这种方法高效而且不需要任何特殊的数据库权限——只需要公共 RPC 节点即可。

英文：How would you do Binary Search to Locate a Block given a TimeStamp (for Any Blockchain)?

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版