【愚公系列】2023年11月 七大查找算法(七)-分块查找
🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
在编程语言中，查找算法是指在一个数据集合中查找某个元素是否存在的算法。常见的查找算法包括：
- 顺序查找（Sequential Search）：逐个遍历数据集来查找目标元素，时间复杂度为O(n)。
- 二分查找（Binary Search）：在有序数据集合中，从中间位置作为起点不断划分区间并查找，时间复杂度为O(log n)。
- 插值查找（Interpolation Search）：在有序数据集合中，根据目标元素与数据集合首尾之间的差值，利用插值估算目标元素的位置，时间复杂度为O(log log n)或O(n)。
- 斐波那契查找（Fibonacci Search）：在有序数据集合中，根据斐波那契数列调整中间点的位置来查找，时间复杂度为O(log n)。
- B树查找（B-Tree Search）：在平衡的B树中查找元素，时间复杂度为O(log n)。
- 哈希查找（Hash Search）：通过哈希函数将元素映射到哈希表中，并在哈希表中查找元素，时间复杂度为O(1)。
- 分块查找（Block Search）：将数据集合划分为若干块，在每个块中进行二分查找或顺序查找，时间复杂度为O(sqrt(n))。
以上算法都有各自适用的场景，开发者需要根据数据集合的特性和需求选择最适合的算法来进行查找。
🚀一、分块查找
🔎1.基本思想
分块查找算法的基本思想是将一个序列分成若干块，每一块内部元素可以任意排列，但是块与块之间必须按照一定的次序排列。同时，每一块内部元素的大小也必须有一定的关系，这样可以使得在查找时可以缩小查找范围。
具体实现时，需要确定每一块的大小和块与块之间的关系。然后在进行查找时，首先确定目标元素所在的块，然后对该块内部进行顺序查找或者使用其他查找算法。如果目标元素不在该块中，则在其他块中进行类似的操作，直到找到目标元素为止。
因为分块查找算法采用了块与块之间必须按照一定的次序排列这一限制条件，可以使得它比普通的顺序查找算法更加高效。但是，需要注意的是，在构建分块查找算法时需要花费一定的时间和空间来预处理块与块之间的关系。
🔎2.复杂度分析
分块查找算法的时间复杂度为 $O(\sqrt{n})$，其中 $n$ 是元素总数。
分块查找算法的思路是将元素分成若干个块，每个块内部有序，块与块之间不一定有序。首先在每个块内部使用二分查找算法进行查找，然后在找到的块中再使用线性查找算法进行查找。这样，每次查找最多需要进行一次二分查找和一次线性查找，时间复杂度为 $O(\sqrt{n})$。因为总共有 $\sqrt{n}$ 个块，所以总时间复杂度为 $O(\sqrt{n})$。
在最坏情况下，所有元素都在同一个块中，此时需要进行一次二分查找和一次线性查找，时间复杂度为 $O(\log n + n)$，但是由于将元素分块，大部分情况下元素都不在同一个块中，平均时间复杂度为 $O(\sqrt{n})$。
🔎3.应用场景
分块查找算法适用于以下应用场景：
- 数据量较大，并且需要在其中快速查找某个元素的位置或值；
- 数据具有一定的有序性，使得分块后的块内元素也有序；
- 数据变化频率较低，即不需要频繁地进行插入、删除等操作。
具体的应用场景包括：
- 图书馆图书的索引查找，按照书名的首字母进行分块，每个块内的书籍按照书名排序；
- 操作系统的文件系统索引，将文件按照目录进行分块，每个目录内的文件按照文件名排序；
- 网络流量监测系统，将流量数据按照时间进行分块，每个时间块内的数据按照IP地址排序；
- 游戏中的地图数据索引，将地图按照坐标进行分块，每个坐标块内的地图数据按照地图元素类型排序。🔎4.示例
namespace IndexSearch.CSharp
{
/// <summary>
/// 索引项实体
/// </summary>
public class IndexItem
{
public int Index { get; set; }
public int Start { get; set; }
public int Length { get; set; }
}
public class Program
{
/// <summary>
/// 主表
/// </summary>
static int[] studentList = new int[] {
101,102,103,104,105,0,0,0,0,0,
201,202,203,204,0,0,0,0,0,0,
301,302,303,0,0,0,0,0,0,0
};
/// <summary>
/// 索引表
/// </summary>
static IndexItem[] IndexItemList = new IndexItem[] {
new IndexItem{ Index=1,Start=0,Length=5},
new IndexItem{ Index=2,Start=10,Length=4},
new IndexItem{ Index=3,Start=20,Length=3}
};
/// <summary>
/// 索引查找算法
/// </summary>
/// <param name="key">给定值</param>
/// <returns>给定值在表中的位置</returns>
public static int IndexSearch(int key)
{
IndexItem item = null;
// 建立索引规则
var index = key / 100;
//遍历索引表,找到对应的索引项
for (int i = 0; i < IndexItemList.Count(); i++)
{
//找到索引项
if (IndexItemList[i].Index == index)
{
item = new IndexItem() { Start = IndexItemList[i].Start, Length = IndexItemList[i].Length };
break;
}
}
//索引表中不存在该索引项
if (item == null)
return -1;
//在主表顺序查找
for (int i = item.Start; i < item.Start + item.Length; i++)
{
if (studentList[i] == key)
{
return i;
}
}
return -1;
}
/// <summary>
/// 插入数据
/// </summary>
/// <param name="key"></param>
/// <returns>true,插入成功，false,插入失败</returns>
public static bool Insert(int key)
{
IndexItem item = null;
try
{
//建立索引规则
var index = key / 100;
int i = 0;
//遍历索引表,找到对应的索引项
for (i = 0; i < IndexItemList.Count(); i++)
{
if (IndexItemList[i].Index == index)
{
item = new IndexItem()
{
Start = IndexItemList[i].Start,
Length = IndexItemList[i].Length
};
break;
}
}
//索引表中不存在该索引项
if (item == null)
return false;
//依索引项将值插入到主表中
studentList[item.Start + item.Length] = key;
//更新索引表
IndexItemList[i].Length++;
}
catch
{
return false;
}
return true;
}
static void Main(string[] args)
{
Console.WriteLine("********************索引查找(C#版)********************\n");
Console.WriteLine("原始数据：{0}",String.Join(" ",studentList));
int value = 205;
Console.WriteLine("插入数据:{0}",value);
//插入成功
if (Insert(value))
{
Console.WriteLine("\n插入后数据:{0}",String.Join(",", studentList));
Console.WriteLine("\n元素205在列表中的位置为:{0} ",IndexSearch(value));
}
Console.ReadKey();
}
}
}腾讯云开发者
