用C语言编写分块查找算法，并分析算法时间复杂度

分块查找（Block Search），也被称为范围查找或分段查找，是一种改进的二分查找算法，它将数组分成若干相等大小的块，然后仅对包含目标值的那部分块进行搜索，而不是从头到尾逐个比较。以下是使用C语言实现的一个简单分块查找的例子：

#include <stdio.h>

// 假设数组元素是整数，块大小为block_size
int block_search(int arr[], int n, int target, int block_size) {
    // 计算块的数量
    int blocks = (n - 1) / block_size + 1;

    // 遍历所有块
    for (int i = 0; i < blocks; ++i) {
        int low = i * block_size;
        int high = std::min((i+1)*block_size - 1, n-1); // 确保不超过数组边界

        if (arr[low] == target || (low < high && arr[high] == target)) { // 如果目标值在块内或者相邻块的边界
            return low; // 返回目标值的索引
        }

        // 如果当前块不存在目标值，则跳过继续搜索下一个块
    }
    
    return -1; // 没有找到目标值，返回-1
}

int main() {
    int arr[] = {1, 4, 7, 9, 11, 15, 26, 38, 42};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 15;
    int block_size = 3;
    int result = block_search(arr, n, target, block_size);
    if (result != -1)
        printf("找到了 %d 的位置: %d\n", target, result);
    else
        printf("%d 不在数组中。\n", target);
    return 0;
}

**时间复杂度分析：**
- 对于每个块，我们进行了一次线性的查找（最坏情况），因此总的查找次数是块的数量，即 O(blocks)。
- 块的数量与数组长度 n 和块大小 block_size 关系密切，当 n 是块大小的倍数时，块的数量最少；如果不是，那么会有额外的一次查找。所以时间复杂度通常表示为 O(log n) 或者最好情况下的 O(1) （当目标值位于最后一个块内），最差情况是 O(n/block_size)。