分块查找要求是顺序表，分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
将n个数据元素"按块有序"划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须"按块有序"；
即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
而第2块中任一元素又都必须小于第3块中的任一元素，……
1、先选取各块中的最大关键字构成一个索引表；
2、查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
3、在已确定的块中用顺序法进行查找。
示例：
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();
}
}
}
时间复杂度：O(log(m)+N/m)
