分块查找详解

1、原理

分块查找（Block Search）是一种结合顺序查找与索引查找的算法，适用于数据分块存储且块内无序但块间有序的场景。它通过“分块-建立索引-逐层定位”提高查找效率。

分块查找的核心思想

1. 数据分块
   将数据集划分为若干块（子表），每个块内的元素可以无序，但块与块之间需满足有序性（例如：第1块的最大值 ≤ 第2块的最小值）。
2. 建立索引表
   记录每块的最大值（或区间）和对应块的起始-结束索引，索引表本身有序。
3. 两步查找
   • 定位块：先在索引表中确定目标值所在的块（顺序查找或二分查找）。
   • 块内查找：在对应的块内进行顺序查找。

分块查找的实现步骤

1. 数据分块与索引表构建

假设数组为 [12, 8, 5, 20, 25, 15, 18, 28, 32, 10]，按最大块值分块：

• 分块示例：

  块1: [12, 8, 5] → 最大值 12

  块2: [20, 25, 15] → 最大值 25

  块3: [18, 28, 32, 10] → 最大值 32

• 索引表：

  块最大值	起始索引	结束索引
  12	0	2
  25	3	5
  32	6	9

2. 查找流程

以查找 28 为例：

1. 定位块：遍历索引表，找到第一个块最大值 ≥ 28 的块（块3）。
2. 块内查找：在块3的索引范围（6~9）内遍历，找到 28。

2、性能分析

• 时间复杂度：
  • 定位块：假设块数为 m，时间复杂度为 ( O(m) )（顺序查找）或 ( O(\log m) )（索引表有序时用二分查找）。
  • 块内查找：块内最大元素数为 s，时间复杂度为 O(s)。
  • 总时间复杂度：O(m+s) 或 O(logm+s)。

• 优化方向

  • 索引表二分查找：若索引表有序，可将定位块的时间优化为对数级。
  • 均匀分块：尽量保证每块元素数量均衡，避免极端情况（如一个块包含绝大多数元素）。

3、适用场景

• 数据动态增减，插入/删除操作频繁（块内无需完全有序）。
• 数据量较大且无法完全装入内存时，分块存储在磁盘中。

4、代码实现

Python:

def block_search(arr, block_ranges, key):# 1. 定位块：顺序查找索引表block_idx = -1for i, (max_val, start, end) in enumerate(block_ranges):if key <= max_val:block_idx = ibreakif block_idx == -1:return -1# 2. 在块内顺序查找start, end = block_ranges[block_idx][1], block_ranges[block_idx][2]for i in range(start, end + 1):if arr[i] == key:return ireturn -1# 示例数据与索引表
arr = [12, 8, 5, 20, 25, 15, 18, 28, 32, 10]
block_ranges = [(12, 0, 2),   # 块1：最大值12，索引0~2(25, 3, 5),   # 块2：最大值25，索引3~5(32, 6, 9)    # 块3：最大值32，索引6~9
]# 查找测试
print(block_search(arr, block_ranges, 28))  # 输出：7（索引位置）
print(block_search(arr, block_ranges, 10))  # 输出：9
print(block_search(arr, block_ranges, 99))  # 输出：-1（未找到）

golang（定义 Block 结构体/类，包含最大值、起始索引和结束索引）:

package mainimport "fmt"// 定义块索引结构
type Block struct {MaxVal   intStartIdx intEndIdx   int
}// 分块查找函数
func blockSearch(arr []int, blocks []Block, key int) int {// 1. 定位块：顺序查找索引表blockIndex := -1for i, block := range blocks {if key <= block.MaxVal {blockIndex = ibreak}}if blockIndex == -1 {return -1}// 2. 块内顺序查找block := blocks[blockIndex]start, end := block.StartIdx, block.EndIdxfor i := start; i <= end; i++ {if arr[i] == key {return i}}return -1
}func main() {// 示例数据与索引表arr := []int{12, 8, 5, 20, 25, 15, 18, 28, 32, 10}blocks := []Block{{MaxVal: 12, StartIdx: 0, EndIdx: 2}, // 块1{MaxVal: 25, StartIdx: 3, EndIdx: 5}, // 块2{MaxVal: 32, StartIdx: 6, EndIdx: 9}, // 块3}// 测试查找fmt.Println(blockSearch(arr, blocks, 28)) // 输出：7fmt.Println(blockSearch(arr, blocks, 10)) // 输出：9fmt.Println(blockSearch(arr, blocks, 99)) // 输出：-1
}

php（使用二维数组表示索引表）:

<?php
class BlockSearch {// 分块查找函数public static function search($arr, $blockRanges, $key) {// 1. 定位块：顺序查找索引表$blockIndex = -1;foreach ($blockRanges as $index => $block) {list($maxVal, $start, $end) = $block;if ($key <= $maxVal) {$blockIndex = $index;break;}}if ($blockIndex == -1) return -1;// 2. 块内顺序查找list($maxVal, $start, $end) = $blockRanges[$blockIndex];for ($i = $start; $i <= $end; $i++) {if ($arr[$i] == $key) {return $i;}}return -1;}
}// 示例数据与索引表
$arr = [12, 8, 5, 20, 25, 15, 18, 28, 32, 10];
$blockRanges = [[12, 0, 2],   // 块1：最大值12，索引0~2[25, 3, 5],   // 块2：最大值25，索引3~5[32, 6, 9]    // 块3：最大值32，索引6~9
];// 测试查找
echo BlockSearch::search($arr, $blockRanges, 28) . "\n"; // 输出：7
echo BlockSearch::search($arr, $blockRanges, 10) . "\n"; // 输出：9
echo BlockSearch::search($arr, $blockRanges, 99) . "\n"; // 输出：-1
?>

java（定义 Block 结构体/类，包含最大值、起始索引和结束索引）:

import java.util.ArrayList;
import java.util.List;class Block {int maxVal;int startIdx;int endIdx;Block(int maxVal, int startIdx, int endIdx) {this.maxVal = maxVal;this.startIdx = startIdx;this.endIdx = endIdx;}
}public class BlockSearch {public static int search(List<Integer> arr, List<Block> blocks, int key) {// 1. 定位块：顺序查找索引表int blockIndex = -1;for (int i = 0; i < blocks.size(); i++) {Block block = blocks.get(i);if (key <= block.maxVal) {blockIndex = i;break;}}if (blockIndex == -1) return -1;// 2. 块内顺序查找Block targetBlock = blocks.get(blockIndex);int start = targetBlock.startIdx;int end = targetBlock.endIdx;for (int i = start; i <= end; i++) {if (arr.get(i) == key) {return i;}}return -1;}public static void main(String[] args) {// 示例数据与索引表List<Integer> arr = new ArrayList<>(List.of(12, 8, 5, 20, 25, 15, 18, 28, 32, 10));List<Block> blocks = new ArrayList<>();blocks.add(new Block(12, 0, 2));   // 块1blocks.add(new Block(25, 3, 5));   // 块2blocks.add(new Block(32, 6, 9));   // 块3// 测试查找System.out.println(search(arr, blocks, 28)); // 输出：7System.out.println(search(arr, blocks, 10)); // 输出：9System.out.println(search(arr, blocks, 99)); // 输出：-1}
}

5、与其他查找算法对比

算法	前提条件	时间复杂度	适用场景
顺序查找	无	O(n)	小规模无序数据
二分查找	数据有序	O(logn)	静态有序数据
分块查找	块间有序，块内无序	O(m+s)	动态数据，分块存储
哈希查找	哈希函数设计合理	O(1)	快速精确查找，无范围查询