分块查找通过“分而治之”实现O(√n)平均时间复杂度：先依索引表（存每块最大值及范围）定位目标块，再在块内顺序查找；块大小与块数均取√n最优，要求块间有序但块内可无序。

分块查找能显著提升海量数据的检索效率，尤其适合数据量大、更新不频繁、又不需要全局严格排序的场景。它的核心不是把整个数组排好序，而是“分而治之”：先快速定位目标在哪一块，再在小范围内顺序查找。实际效果接近 O(√n)，比纯顺序查找快得多，又比二分查找对数据结构的要求低。

分块前的关键准备：合理划分块大小

块太大，块内查找慢；块太小，索引表膨胀，块间查找开销大。最优策略是让块数 ≈ 块长 ≈ √n（n为数组总长度）。例如 100 个元素，就分约 10 块，每块 10 个元素。这能平衡两阶段开销：

• 块间查找最多比较 √n 次（用顺序或折半都可）
• 块内查找平均比较 √n/2 次
• 整体平均时间复杂度稳定在 O(√n)

构建索引表：只存每块的关键特征

索引表不必存整块数据，只需记录每块的最大值和起始/结束下标。前提是块间有序（前一块所有元素 ≤ 后一块所有元素），这是分块查找高效的前提。例如数组 {5, 12, 9, 16, 21, 18, 32, 23, 37} 可按规则划分为：

• 块1（下标 0–3）：{5,12,9,16} → 最大值 = 16
• 块2（下标 4–6）：{21,18,32} → 最大值 = 32
• 块3（下标 7–8）：{23,37} → 最大值 = 37

索引表就是 [{max:16, start:0, end:3}, {max:32, start:4, end:6}, {max:37, start:7, end:8}] —— 轻量、易维护。

两步查找：先定块，再查数

查找目标值时，分两个明确阶段执行：

• 第一阶段（块定位）：遍历索引表，找第一个满足 target ≤ 块.max 的块。例如查 25，16
• 第二阶段（块内扫描）：在块2对应下标范围 [4,6] 内顺序比对：arr[4]=21, arr[5]=18, arr[6]=32 → 找到或确认不存在

即使块内无序，只要块间有序，这个逻辑就成立。无需对原始数组做任何排序，仅需预处理一次索引表。

实战优化点：动态适配与边界处理

真实应用中要注意几个细节，否则容易出错：

• 最后一块长度常不足 √n，计算 end 下标时要用 Math.min(start + blockSize - 1, n - 1)
• 若数据会增删，优先更新索引表中的 max 和范围，而不是重排整个数组
• 当块间不自然有序（如原始数据杂乱），可改为每块记录 min 和 max，查找时判断 min ≤ target ≤ max，但性能略降
• 索引表本身可用数组或 ArrayList 存储，查找时对索引表用二分（因它天然有序），进一步压到 O(log √n) + O(√n)