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

分块查找详解

news 2025/5/30 18:22:29

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.xdnf.cn/news/677809.html

相关文章：

  • 第二章 1.3 数据采集风险的现有技术和解决方案
  • RK3568 OH5.1 镜像烧录
  • python第34天打卡
  • 深耕数字化赛道，联众优车以创新风控体系构筑汽车金融护城河
  • Fine-tuning：微调技术，训练方式，LLaMA-Factory，ms-swift
  • AI智能分析网关V4垃圾桶满溢检测算法打造城市/公园/街道等场景应用方案
  • 浅谈Mysql的MVCC机制（RC与RR隔离级别）
  • LeetCode 1696. 跳跃游戏 VI（中等）
  • AI Agent开发第75课-数据、张量、流水线并行全解析
  • 【Web应用】若依：基础篇03-入门案例，若依代码生成器生成前后端代码
  • Web通信协议全景解析：从HTTP到WebService的技术演进与对比
  • 如何寻找大模型在企业业务中的价值？
  • Anaconda下载安装+配置虚拟环境保姆级教程（2025版）
  • 实时数仓flick+clickhouse启动命令
  • 第一个ASP.NET项目
  • 【Elasticsearch】retry_on_conflict
  • Python中while 1和while True有何区别？深入解析无限循环的写法选择
  • 百胜咨询公司：企业EcoVadis认证的专业导航者
  • SIGGRAPH 2025 | 快手可灵团队提出3D感知的电影级文本到视频生成框架CineMaster
  • 鸿蒙5开发宝藏案例分享---一多断点开发实践
  • 0527漏洞原理：SQL注入笔记 SQL注入类型（联合查询注入、报错注入实操）
  • 【本地部署】 Deepseek+Dify创建工作流
  • 【Vue 3 运行时 Diff 算法深度解析：五步走策略实现高效更新】
  • MySQL数据库第一章
  • 科技趋势分析系统 BBC (Big Bang of Computing)
  • mysql中的索引怎么用？
  • [特殊字符]《计算机组成原理》第 8 章 - CPU 的结构和功能
  • 本地部署 DeepSeek
  • 计算机组成原理——指令的寻址方式
  • 迪米特法则 (Law of Demeter, LoD)