当前位置： 首页 > article >正文

分块查找详解

article 2025/8/18 22:30:19

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)

快速精确查找，无范围查询

 

http://www.lryc.cn/news/2387507.html

相关文章：

  • leetcode hot100刷题日记——21.不同路径
  • Elasticsearch 如何实现跨数据中心的数据同步？
  • C语言学习笔记三 --- V
  • 通过JS模板引擎实现动态模块组件(Vite+JS+Handlebars)
  • 梯度消失和梯度爆炸的原因及解决办法
  • 欧拉定理：若 gcd(a,n)=1，则 a^φ(n)≡1(mod n)。
  • fvm install 下载超时 过慢 fvm常用命令、flutter常用命令
  • Python正则表达式：30秒精通文本处理
  • Introduction to SQL
  • 计算机视觉---YOLOv3
  • #RabbitMQ# 消息队列进阶
  • React从基础入门到高级实战：React 核心技术 - React Router：路由管理
  • 【深度学习】损失“三位一体”——从 Fisher 的最大似然到 Shannon 的交叉熵再到 KL 散度，并走进 PET·P-Tuning微调·知识蒸馏的实战
  • 5 分钟速通密码学！
  • Linux——IP协议
  • Lua 脚本在 Redis 中的运用-24 （使用 Lua 脚本实现原子计数器）
  • Linux信号量(32)
  • 技术视界 | 打造“有脑有身”的机器人：ABC大脑架构深度解析（上）
  • 使用堡塔和XShell
  • 软件项目交付阶段，验收报告记录了什么？有哪些标准要求？
  • LightGBM的python实现及参数优化
  • 封装渐变堆叠柱状图组件附完整代码
  • 分布式项目保证消息幂等性的常见策略
  • 山东大学软件学院创新项目实训开发日志——第十三周
  • 如何在sublime text中批量为每一行开头或者结尾添加删除指定内容
  • Cesium 透明渐变墙 解决方案
  • 网络原理与 TCP/IP 协议详解
  • day022-定时任务-故障案例与发送邮件
  • 新增 git submodule 子模块
  • List优雅分组