遍写算法，利用折半查找实现确定记录所在块的分块查找

分块查找（Block Search）是一种基于分块思想的查找算法。它将数据集合分成若干块，并在每一块中选取一个关键字最大的元素作为该块的索引项，这些索引项按照关键字有序排列，构成一个索引表。对于给定的查找关键字，先在索引表中进行折半查找，找到包含该关键字的块，再在该块中顺序查找，就可以得到查找结果。

具体实现如下：

def block_search(arr, block_size, target):
    n = len(arr)
    # 计算块数
    num_blocks = (n + block_size - 1) // block_size
    # 构建索引表
    index_table = []
    for i in range(num_blocks):
        start = i * block_size
        end = min(start + block_size, n)
        max_val = max(arr[start:end])
        index_table.append((max_val, start, end))
    # 在索引表中进行折半查找
    left, right = 0, num_blocks - 1
    while left <= right:
        mid = (left + right) // 2
        if target > index_table[mid][0]:
            left = mid + 1
        elif target < index_table[mid][0]:
            right = mid - 1
        else:
            start, end = index_table[mid][1], index_table[mid][2]
            # 在找到的块中顺序查找
            for i in range(start, end):
                if arr[i] == target:
                    return i
            return -1  # 没有找到
    return -1  # 没有找到

其中，`arr` 为待查找的数组，`block_size` 为块大小，`target` 为待查找的关键字。函数首先计算出数组中的块数，然后依次遍历每个块，找到该块中的最大值，并记录该块的起始位置和结束位置，构建索引表。接下来，在索引表中进行折半查找，找到包含目标关键字的块后，在该块中顺序查找目标关键字，返回其位置。如果没找到，则返回 `-1`。