正文

算法实践分块查找知多少？手把手带你实现分块查找

author  author  2022-12-24  436

关键词：

前言

什么是分块查找？

分块查找又称索引顺序查找，是折半查找和顺序查找的一种改进方法，由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。折半查找其实也算是分块查找的特殊用法，分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。

需要注意的是，当节点变化很频繁时，可能会导致块与块之间的节点数相差很大，没写快具有很多节点，而另一些块则可能只有很少节点，这将会导致查找效率的下降。

分块查找的基本思想：分块查找要求将n个数据元素划分为m块（m小于等于n）。每一块的数据不必有序，但块与块之间必须有序，也就是说第一块中任意一个元素都必须小于第二块中任意一个元素，而第二块中任意一个元素又都必须小于第三块中任意一个元素，

分块查找的核心是构建索引表，索引表包括两个字段，即关键码，（存放对应子表中的最大关键字）和指针字段（存放指向对应子表的指针），索引表按关键码字段有序排序。通过最大关键字与起始地址确定其具体位置。

图解分块查找

分块查找设计

查找图示

【算法实践】分块查找知多少？手把手带你实现分块查找_分块查找

查找过程

分块查找的过程分为两步：

第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表
第二步是在块内顺序查找

【算法实践】分块查找知多少？手把手带你实现分块查找_分块查找_02

代码实现

根据上图可得出基本步骤如下:

输入待查的目标数据
把最大值作为索引值
判断待查数据是否大于索引值,如果大于索引值,那么比较下一块数据的索引值,否则得到当前当前待查找数据所在块的索引
通过顺序查找得到待查找数据在块中的位置
返回目标数据的位置

代码如下:

定义相关参数

Length = 8 #输入元素的个数
targets = 0
pos = -1
tabNum = 3 #分块
tabPos = -1
print("请输入列表，以空格键隔开数字:",end= )
list=[int(s) for s in input().split()]
goal = int(input(请输入待查元素：))   #用户输入查找值
print(需要在列表中在找到：, goal)

排序后建立索引，根据索引建立子列表,并显示构造的子列表:

list_index = []  #使用二维列表表示多个子序列
for i in range(tabNum):  # 在列表中添加m个列表
    list_index.append([])
for i in range(1, tabNum):  
    list_index[i].append(list[i - 1])  
for i in range(1, tabNum - 1):  # 将添加元素的子列表中的元素降序排列
    for j in range(1, tabNum - i):
        if list_index[j] < list_index[j + 1]:
            list_index[j], list_index[j + 1] = list_index[j + 1], list_index[j]
for i in range(tabNum - 1, Length):  
    for j in range(1, tabNum):
        if list[i] > list_index[j][0]:
            list_index[j - 1].append(list[i])
            break
    else:
        list_index[tabNum - 1].append(list[i])
if len(list_index[0]) > 1:  
    for i in range(len(list_index[0]) - 1, 0, -1):
        if list_index[0][i] > list_index[0][i - 1]:
            list_index[0][i], list_index[0][i - 1] = list_index[0][i - 1], list_index[0][i]
print("子列表结构：",list_index)  # 输出子列表

将给定的目标元素与各个子列表进行比较,确定目标元素所在位置,标记并返回,若找到则输出目标元素所在位置,否则输出:"没找到" 。下面就是见证奇迹的时刻：

for i in range(tabNum - 1, -1, -1):  #确定给定元素位置
    if len(list_index[i]) != 0 and goal < list_index[i][0]:
        for j in range(len(list_index[i])):
            if list_index[i][j] == goal:
                tabPos = i + 1
                pos = j + 1
                targets = 1

if targets:
    print("在第", tabPos,"个子列表中第",pos,"的位置")
else:
    print("没找到")

执行结果如下：

【算法实践】分块查找知多少？手把手带你实现分块查找_分块查找_03

总结

分块查找的平均查找长度由两部分组成，一个是对索引表进行查找的平均查找长度，一个是对块内节点进行查找的平均查找长度，总的平均查找长度为E(n)=+。线性表中共有n个节点，分成大小相等的b块，每块有s=n/b个节点。假定读索引表也采用顺序查找，只考虑查找成功的情况，并假定对每个节点的查找概率是相等的，则对每块的查找概率是1/b，对快内每个节点的查找概率是1/s。

分块查找在现实生活中也很常用。比如:公司有不同的部门,每个员工都有属于自己的工号;且每个部门的员工档案是放在不同的文件夹中,当你要找一个员工的档案时,最快的方法是确定他所在的部门,然后在对应的部门档案文件夹中逐一查找对应的员工档案。再比如:在一个小区有很多单元,每栋楼都有很多住户,如果你是快递员,要送货上门，精准投递的通常最好做法就是确定客户住在几单元,楼层,房号多少，在这里单元可作为分块划分的依据,楼层也可作为分块划分的依据,可根据具体情况设定。现实生活中，一般以单元号划分块基本就能精准送达

c语言试题178之实现分块查找算法，索引顺序查找算法

查看详情

分块查找的思及其查找效率分析（c语言）(代码片段)

一、分块查找（一）算法思想//索引表typedefstruct ElemTypemaxValue; intlow,high;Index;//顺序表存储实际元素ElemTypeList[100];特点：块内无序、块间有序分块查找，又称索引顺序查找，算法过程如下：①在索引表中确定... 查看详情

scala练习-分块查找

...，Range分区器的原理中边界划定时就用到了分块查找算法，当时不知道这个名词，今天学习的时候，发现原理就是分块查找啊。多学习肯定没错的，一下子加速我的理解。代码packageday15importday14.Utils/***Createdbydoc... 查看详情

王道数据结构7（查找）

...序表3.顺序查找优化—被查概率不相等三、折半查找（1）算法思想（1）算法实现（3）折半查找判定树的构造（4）查找效率四、分块查找（1）算法分析（2）查找效率分析ASL（3）优化—有规律的分块（4）拓展五、B+树一、概念查... 查看详情

王卓数据结构与算法之查找算法(代码片段)

...目录标题✍、目录脑图1、查找1.1、查找的分类1.2、查找算法的评价指标1.3、线性表的查找1.3.1、顺序查找(线性查找)1.3.1.1、顺序查找性能分析1.3.1.2、顺序查找的特点1.3.2、折半查找(二分查找)1.3.2.1、折半查找性能分析1.3.2.2、折... 查看详情

顺序查找折半查找分块查找

查看详情

算法实践|手把手带你实现快速排序算法

...分析，接着写了关于经典的冒泡排序算法《利用Python手把手带上实现冒泡排序》，算法虽然枯燥，但是当你深入了解就会感受到其中的趣味。在算法的学习中不但可以学会如何思考问题，提高自己的逻辑能力，还能在这... 查看详情

查找——分块查找

文章目录分块查找的概念分块查找的基本思想分块查找的平均查找长度分块查找的概念当数据表中的数据元素很多时，可以采用分块查找。分块查找又称为索引顺序查找。它汲取了顺序查找和折半查找各自的优点，既有... 查看详情

leetcode查找算法（顺序查找，二分法，斐波那契查找，插值查找，分块查找）(代码片段)

...代码4.插值查找原理代码5.分块查找原理代码参考查找算法也可以叫搜索算法。就是从一个有序数列中找出一个特定的数，常用于判断某个数是否在数列中，或者某个数在数列中的位置。在计算机应用中，查找是常... 查看详情

(王道408考研数据结构)第七章查找-第二节3：分块查找

文章目录一：分块查找基本思想二：注意问题三：效率分析一：分块查找基本思想分块查找：我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项。分块有序具体是指块内无序：也即块内的记录不要求有... 查看详情

(王道408考研数据结构)第七章查找-第二节3：分块查找

手把手教你实现一个完整的bst(超级详细)

查找基本分类如下：线性表的查找顺序查找折半查找分块查找树表的查找二叉排序树平衡二叉树B树B+树散列表的查找今天介绍二叉排序树。二叉排序树(BinarySortTree)又称为二叉查找树，它是一种对排序和查找都很有用的特殊二叉... 查看详情

静态查找表：顺序查找折半查找分块查找

引言：除去各种线性和非线性的数据结构外。另一种在实际应用中大量使用的数据结构——查找表。查找表是由同一类型的数据元素构成的集合。对查找表常常进行的操作有：1、查找某个"特... 查看详情

算法实践|一步步手把手带你实现寻找最小公倍数

前言其实最小公倍数的概念和计算最小公倍数的方法.那是我们在学习小学数学的时候就已经掌握的数学知识,为了更加通俗易懂一点,本文先从一个分元宝的故事入手:亡故的先父留下遗嘱，共有遗产17个元宝，老大得元宝的二分之... 查看详情

分块查找

分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。构造一个索引表。其中每个索引项... 查看详情

数据结构：查找(代码片段)

...以及平均查找长度等。（2）重点掌握线性表上各种查找算法，包括顺序查找、折半查找和分块查找的基本思路、算法实现和查找效率等。（3）掌握各种树表的查找算法，包括二叉排序树、AVL树、B-树和B+树的基本思路、算法实现... 查看详情

查找算法

1.顺序查找（不在讨论）2.二分查找，插值查找，斐波那契查找3.树表查找4.分块查找5.哈希查找publicfunctionBinarySearch($a=array(),$val,$n)$low=0;$high=$n-1;$mid=0;while($low<=$high)????$mid=($low+$high)/2;????if($a[$mid]===$value)????????? 查看详情

算法7五大查找之：索引查找

...查找，然后在确定的块中进行顺序查找。在实现索引查找算法前需要弄清楚以下三个术语。（1）主表。即要查找的序列。（2）索引项。一般我们会将主表查看详情