Python分块查找

# Python中的分块查找可以通过以下步骤实现：
# 1. 首先将列表分成若干个块（子表），块的长度均匀，最后一块可以不满。
# 2. 每块内部无序，但是块与块之间要求有序。
# 3. 构造一个索引表，其中每个索引项对应一个块，并记录每块的起始位置以及每块中最大的关键字（或者最小的关键字）。
# 4. 索引表按照关键字有序排列。

# 以下是一个简单的Python分块查找的示例代码：
def chunk_search(arr, chunk_size, key):
    # 将列表分块
    chunks = [arr[i:i + chunk_size] for i in range(0, len(arr), chunk_size)]
    
    # 对每个块进行排序
    for chunk in chunks:
        chunk.sort()
    
    # 构造索引表
    index_table = [(chunk[0], chunk[-1]) for chunk in chunks]
    
    # 对索引表按照关键字排序
    index_table.sort(key=lambda x: x[0])
    
    # 在索引表中查找对应的块
    for start, end in index_table:
        if start <= key <= end:
            chunk_index = index_table.index((start, end))
            break
    
    # 在对应的块中进行查找
    chunk = chunks[chunk_index]
    if key in chunk:
        return f"The key {key} is found in chunk {chunk_index} at index {chunk.index(key)}"
    else:
        return "Key not found"

# 示例使用
arr = [3, 7, 2, 11, 15, 9, 1, 5, 8, 17, 13, 19, 21]
chunk_size = 4
key = 13
result = chunk_search(arr, chunk_size, key)
print(result)  # 输出：The key 13 is found in chunk 2 at index 2