分块查找python

分块查找（Block Search）是一种在有序列表中查找目标元素的算法。它将列表分成若干块，每个块的大小可以根据实际情况确定。首先，确定目标元素所在的块，然后在该块中进行顺序查找。如果找到目标元素，则返回其索引；如果在块中未找到目标元素，则说明目标元素不在该块中，继续在下一个块中进行查找，直到找到目标元素或遍历完所有块。

以下是一个使用分块查找算法的Python示例：

def block_search(arr, target):
    block_size = int(len(arr) ** 0.5)  # 块的大小
    block_index = -1  # 目标元素所在的块索引

    # 确定目标元素所在的块
    for i in range(0, len(arr), block_size):
        if arr[i] >= target:
            block_index = i
            break

    # 在目标块中进行顺序查找
    for i in range(block_index, min(block_index + block_size, len(arr))):
        if arr[i] == target:
            return i

    return -1  # 目标元素不存在

# 示例使用
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
target = 13
index = block_search(arr, target)
print("目标元素的索引：", index)  # 输出：6