algorithm for binary search of RPC to find transactions by nonce

algo.py

from typing import Iterator                                                                                                                                                           
                                                                                                                                                                                      
blockchain: tuple[list[int], ...] = ([], [0], [1, 2], [], [], [], [3, 4], [5, 6, 7], [8, 9])                                                                                          
                                                                                                                                                                                      
                                                                                                                                                                                      
def get_txns(blk):                                                                                                                                                                    
    print("eth_getReceipt", blk, "->", blockchain[blk])                                                                                                                               
    return iter(blockchain[blk])                                                                                                                                                      
                                                                                                                                                                                      
                                                                                                                                                                                      
def num_txns_at_blk(blk):       
    num_txns = sum(len(blockchain[i]) for i in range(blk + 1))
    print("eth_getTransactionCountAtBlock", blk, "->", num_txns)
    return num_txns      
                                                                                           
                                                                                           
def find_blocks(   
    start_nonce: int, stop_nonce: int, start_block: int, stop_block: int
) -> Iterator[int]:
    if start_block == stop_block:
        # Honed in on one block where there's a delta in nonce, so must be the right block
        for txn in get_txns(stop_block):
            if txn >= start_nonce:
                yield txn                                                                  
        return                          
                                             
    # bisect             
    blk = start_block + (stop_block - start_block) // 2 + 1  # bias towards stop_block
    num_txns = num_txns_at_blk(blk - 1)
                                             
    if start_nonce < num_txns:                                                             
        yield from find_blocks(start_nonce, min(num_txns - 1, stop_nonce), start_block, blk - 1)

    if num_txns <= stop_nonce:
        yield from find_blocks(max(start_nonce, num_txns), stop_nonce, blk, stop_block)                                                                                               


nonce = max(max(b) for b in blockchain if b)
print(*find_blocks(0, nonce, 0, len(blockchain) - 1))
print(*find_blocks(0, nonce // 2, 0, len(blockchain) - 1))
print(*find_blocks(nonce // 2, nonce, 0, len(blockchain) - 1))