首页 > 代码库 > 静态查找表：顺序查找、折半查找、分块查找
静态查找表：顺序查找、折半查找、分块查找
引言：
除去各种线性和非线性的数据结构外。另一种在实际应用中大量使用的数据结构——查找表。查找表是由同一类型的数据元素构成的集合。
对查找表常常进行的操作有：1、查找某个"特定的"数据元素是否在查找表中；2、检索某个"特定的"数据元素的各种属性；3、在查找表中插入一个数据元素；4、从查找表中删去某个数据元素。对查找表仅仅作前两种统称为"查找"的操作，则称此类查找表为静态查找表。
若在查找过程中同一时候插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表。
基础知识：
keyword类型和数据元素类型统一说明例如以下：
典型的keyword类型说明能够是：
typedef float KeyType; //实型
typedef int KeyType; //整型
typedef char KeyType; //字符串型
数据元素类型定义为：
typedef struct {
KeyType key; //keyword域
........ //其它域
}SElmType;
对两个keyword的比較约定例如以下的宏定义：
//对数值型keyword
#define EQ(a, b) ((a) == (b))
#define LT(a, b) ((a) < (b))
#define LQ(a, b) ((a) > (b))
//对字符串型keyword
#define EQ(a, b) (!strcmp((a), (b)))
#define LT(a, b) (strcmp((a), (b)) < 0)
#define LQ(a, b) (strcmp((a), (b)) > 0) 详细分析：
1、顺序查找。
顺序查找：从表中最后一个记录開始。逐个进行记录的keyword和给定值的比較，若某个记录的keyword和给定值比較相等，则查找成功，找到所查记录；反之。若直至第一个记录，其keyword和给定值比較都不相等，则表明表中没有所查记录。查找不成功。
性能分析：我们知道当讨论一个程序的性能时一般从3个角度：时间复杂度、空间复杂度、和算法的其它性能。因为在查找过程中。通常仅仅是须要一个固定大小的辅助空间来做比較，所以空间复杂度是一定的。而时间复杂度却是可变的：其keyword和给定值进行过比較的记录个数的平均值。
适用范围：顺序查找一般适用于查找数据比較少的情况下。
长处：
1、算法实现简单且适应面广
2、对表的结构无不论什么要求，不管记录是否按keyword有序排列。
3、即适用于顺序表又适用于单链表。
缺点：
1、平均查找长度较大，特别是当n非常大时，查找效率较低。
2、速度慢，平均查找长度为 (n + 1) / 2。时间复杂度为 O(n)
typedef int ElementType;
#define EQ(a, b) ((a) == (b))
int sequential(int Array[], ElementType key, int n)
{
int index;
for(index = 0; index < n; index++){
if(EQ(Array[index], key))
return index + 1;
}
return -1;
} 2、折半查找。
折半查找：折半查找又称二分查找，先确定待查记录所在的范围（区间）。然后逐步缩小范围直到找到或找不到该记录为止。
适用范围：对于规模较大的有序表查找。效率较高。适合非常少修改但常常查找的表。
长处：
1、折半查找的效率比顺序查找要高。
2、折半查找的时间复杂度为log2(n)
3、折半查找的平均查找长度为log2(n+1) - 1
缺点：
1、折半查找仅仅适用于有序表
2、折半查找限于顺序存储结构，对线性链表无法有效地进行折半查找
keywordkey与表中某一元素array[i]比較，有3中情况：
1. key == array[i]， 查找成功
2.key > array[i], 待查找元素可能的范围是array[i]之前
3.key < array[i], 待查找元素可能的范围是array[i]之后
typedef int ElementType;
#define EQ(a, b) ((a) == (b))
#define LT(a, b) ((a) < (b))
#define LQ(a, b) ((a) <= (b))
int Search_Bin(ElementType Array[], int num, int length)
{
int index_low, index_mid, index_high;
index_low = 1;
index_high = length;
while(index_low <= index_high){
index_mid = (index_low + index_high) / 2;
if(EQ(num, Array[index_mid]))
return index_mid + 1;
else if (LT(num, Array[index_mid]))
index_high = index_mid - 1;
else
index_low = index_mid + 1;
}
return -1;
} 3、分块查找。
分块查找：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。将n个数据元素“按块有序”划分为m块（m<=n）。每一块中的数据元素不必有序，但块与块之间必须“按块有序”，即第1快中的任一元素的keyword都必须小于第2块中任一元素的keyword；而第2块中任一元素又都小于第3块中的任一元素，……
操作步骤：
1、先选取各快中的最大keyword构成一个索引表
2、查找分两部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中。然后在已确定的快中用顺序法进行查找。
长处：在表中插入或删除一个记录时，仅仅要找到该记录所在块，就在该块中进行插入或删除运算（因快内无序，所以不须要大量移动记录）。
缺点：添加了一个辅助数组的存储空间和将初始表分块排序的运算。
性能：介于顺序查找和二分查找之间。
#define MAX 3
#define MAXSIZE 18
typedef int ElemType;
typedef struct IndexItem{
ElemType index;
int start;
int length;
}IndexItem;
IndexItem indexlist[MAX];
ElemType MainList[MAXSIZE] = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};
int sequential(IndexItem indexlist[], ElemType key)
{
int index;
if(indexlist[0].index >= key) return 1;
for(index = 1; index <= MAX; index++){
if((indexlist[index-1].index < key)&&(indexlist[index].index >= key))
return index+1;
}
return 0;
}
int mainsequential(ElemType MainList[], int index, ElemType key)
{
int i, num=0;
for(i = 0; i < index-1; i++){
num += indexlist[i].length;
}
for(i = num; i < num+indexlist[index-1].length; i++){
if(MainList[i] == key) return i+1;
}
return -1;
} 除上面介绍的3种查找方法，还有针对有序表的斐波那契查找和插值查找以及静态树表的查找。
静态查找表：顺序查找、折半查找、分块查找