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

A couple of days ago, I wanted to look up the block numbers of some important records on the STEEM blockchain — such as when I:

• registered my account #4253590
• became a witness #20190755
• mined my first block #20390040
• was delegated SP by Justin Sun #41676911
• and received a DAO payout #95403889

I only knew the timestamps but not the exact block numbers, so I thought of using Binary Search to locate them.

It is definitely doable. However, sometimes it might be quicker to use the **SDS API**, since this information can be retrieved by a simple query against the database.

That said, because the `steemd` API is publicly available, we don’t have to rely on external services. Instead, we can write a small function that performs a binary search directly against the blockchain.

For example, consider the following Python skeleton:

# Call steemd API to get the timestamp of a given block number.
def get_timestamp_from_block(block_num):
    pass

# Query steemd API to return the latest block number and its timestamp.
# Example return: (block_num, timestamp)
def get_latest_block_and_timestamp():
    pass

# Binary search to locate the block number that is closest to the target timestamp.
def get_block_from_timestamp(target_ts):
    # Step 1: Get latest block and its timestamp
    latest_block, latest_ts = get_latest_block_and_timestamp()
    
    # Step 2: Define search boundaries
    left, right = 1, latest_block
    result = None
    
    # Step 3: Binary search loop
    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  # exact match
    
    return result

Scenarios Where Binary Search Can Be Used

In a search space, if the variable x increases or decreases monotonically, and the function value f(x) also changes monotonically, then binary search can be used to quickly locate a target value or the interval that satisfies a condition.

Common scenarios for binary search include:

• Finding a block number on a blockchain by timestamp (timestamps increase with block numbers).
• Searching for a target value or boundary in a sorted array.
• Finding a threshold that satisfies a condition in a monotonic function (e.g., cost function or probability function).
• Narrowing down the answer range in optimization problems, such as minimizing a cost function.

As long as the problem satisfies monotonicity, binary search can solve it in O(log N) time, which is much more efficient than a linear scan.

How to Get Block given a Timestamp using Binary Search Algorithm?

Take steem blockchain for example:

Fetch timestamps from blocks

By calling the `steemd` or other blockchain API, we can easily get the timestamp associated with any block.

Find the latest block

This gives us an upper bound for the binary search.

Binary search for the target timestamp

Instead of scanning blocks linearly (which would be painfully slow), we halve the search space at each step. This reduces the complexity to about `O(log N)` where `N` is the current block height. This is the beauty of Binary Search which is rated 1 of the top 10 algorithms that are invented by human so far.

Why This Matters?

If you want to map real-world events (with timestamps) to their corresponding block numbers, this approach is efficient and doesn’t require any special database access — just the public RPC node.

–EOF (The Ultimate Computing & Technology Blog) —