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

分块查找是一种常见的数据结构，在大量数据中快速查找指定元素。它将数据分成若干个块，并在每个块中选出一个代表元素，称为块首元素。这些块首元素按照关键字有序排列，形成一个索引表。在查找时，首先在索引表中进行折半查找，找到关键字所在的块首元素，然后再在该块中进行顺序查找，直到找到目标元素。

具体实现如下：

int blockSearch(int *arr, int n, int key, int blockSize) {
    int blockIndex = binarySearch(arr, 0, n / blockSize, key, blockSize);  // 在索引表中进行折半查找
    if (blockIndex == -1) {
        return -1;  // 如果没找到，直接返回-1
    }
    int left = blockIndex * blockSize;
    int right = min(left + blockSize, n);
    for (int i = left; i < right; i++) {  // 在对应块中进行顺序查找
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

int binarySearch(int *arr, int left, int right, int key, int blockSize) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid * blockSize] < key) {
            left = mid + 1;
        } else if (arr[mid * blockSize] > key) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

其中，`arr`是待查找的数组，`n`是数组长度，`key`是要查找的元素，`blockSize`是块大小。`blockSearch`函数中，首先在索引表中进行折半查找，找到关键字所在的块首元素所在的索引位置 `blockIndex`。然后计算出对应块的左右边界 `left` 和 `right`，在该范围内进行顺序查找。如果找到了目标元素，返回其下标，否则返回-1。`binarySearch`函数是折半查找的实现，其输入参数和输出值与标准的折半查找函数类似。