分块查找 | 寻觅~流光

一、概念与原理

分块查找（Block Search），又称为索引顺序查找，是对顺序查找的优化。其核心思想是将数据划分成若干“块”，通过构建每块的索引表来快速定位目标数据所在的块，再在对应的块中顺序查找目标值。

二、算法特点

适用场景：
- 数据量较大，且查询频繁。
- 数据较为稳定（修改较少）。
优势：
- 提高查找效率：先通过索引缩小范围，再在小范围内查找。
- 易于实现，结构简单。
劣势：
- 动态更新数据时，重新构建索引的开销较大。

三、算法实现步骤

1. 数据分块

将数据按照一定规则划分为若干块：

每块的数据可以是连续的。
每块的数据数量相同或接近。
数据可以按照大小排序（便于构建索引）。

2. 构建索引

为每块构建索引表，索引存储以下信息：

每块的范围（例如，块的最大值）。
每块的起始位置（方便快速访问）。

3. 查找流程

索引查找：利用索引定位目标值所在块。
块内查找：在定位的块内，顺序查找目标值。

四、算法时间复杂度

构建索引：O(n)O(n)O(n) （只需遍历数据一次）。
查找时间：
- 索引查找：O(n)O(\sqrt{n})O(n) （如果块数是 n\sqrt{n}n）。
- 块内查找：O(n)O(\sqrt{n})O(n) （块的平均大小是 n\sqrt{n}n）。
- 总体复杂度：O(n)O(\sqrt{n})O(n)。
插入和删除：
- 如果频繁插入或删除，需要重新划分块并构建索引，复杂度较高。

五、代码实现

以下是一个 C++ 实现示例：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 分块查找类
class BlockSearch {
private:
    vector<int> data;        // 原始数据
    vector<int> blocks;      // 每块的最大值
    int blockSize;           // 每块的大小

public:
    // 构造函数：初始化分块
    BlockSearch(vector<int> &input) {
        data = input;
        blockSize = sqrt(data.size()); // 每块大小为 √n
        buildBlocks();
    }

    // 构建块索引
    void buildBlocks() {
        blocks.clear();
        int maxInBlock = INT_MIN;

        for (size_t i = 0; i < data.size(); ++i) {
            maxInBlock = max(maxInBlock, data[i]);
            if ((i + 1) % blockSize == 0 || i == data.size() - 1) {
                blocks.push_back(maxInBlock);
                maxInBlock = INT_MIN;
            }
        }
    }

    // 查找目标值
    int search(int target) {
        // 索引查找
        int blockIndex = -1;
        for (size_t i = 0; i < blocks.size(); ++i) {
            if (target <= blocks[i]) {
                blockIndex = i;
                break;
            }
        }

        if (blockIndex == -1) {
            return -1; // 未找到
        }

        // 块内查找
        int start = blockIndex * blockSize;
        int end = min((blockIndex + 1) * blockSize, (int)data.size());
        for (int i = start; i < end; ++i) {
            if (data[i] == target) {
                return i; // 返回目标值索引
            }
        }

        return -1; // 未找到
    }
};

int main() {
    vector<int> data = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    BlockSearch bs(data);

    int target = 13;
    int result = bs.search(target);

    if (result != -1) {
        cout << "Found " << target << " at index " << result << endl;
    } else {
        cout << target << " not found" << endl;
    }

    return 0;
}