Sparse index lookup
An SSTable uses a sparse index: only the FIRST key of each data block is indexed. You are given `block_first_keys`, a list of the first integer key of each block in ascending block order (so the list is sorted ascending and all blocks are non-empty and key ranges don't overlap). For a list of point-lookup `queries` (integer keys), return for each query the 0-based index of the block that MUST be scanned to find it: the block whose first key is the largest first-key <= the query. If the query is smaller than the first block's first key, the key cannot exist, so return -1 for that query. Return the list of block indices, one per query in order. <= 10^5 blocks and queries.
sparse_index_lookup(block_first_keys: list[int], queries: list[int]) → list[int][[10,20,30],[25,10,5]]out[1,0,-1]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[10,20,30],[25,10,5]][1,0,-1]not run yetsample