1. 查找的基本概念
查找表：同一类型的数据元素的集合。
关键字：关键字是数据元素或记录中某个数据项的值，用它可以标识一个数据元素或记录。若此关键字可以唯一地标识一个记录，则成此关键字为主关键字，反之，称用以识别若干记录的关键字为次关键字。
查找：查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值得记录或数据元素。若表中存在这样一个记录，则称查找成功，否则，查找失败。
动态查找：若在查找过程中对表做修改操作（如插入和删除），则相应的表称之为动态查找，否则称之为静态查找。
2. 线性表的查找
(1)顺序查找
从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功，反之。查找失败。
顺序查找方法即适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。
时间复杂度：T(n) = O(n)。
空间复杂度：S(n) = O(n)。
数据元素定义：
typedef struct{
keyType key;//关键字域
InfoType otherinfo;//其他域
}ElemType;
顺序表的定义：
typedef struct{
ElemType *R;//存储空间基地址
int length;//当前长度
}SSTable;
1. 顺序查找
int Search_Seq(SSTable ST,keyType key)
{
for(i=ST.length;i>=1;i--)
if(ST.R[i].key == key) return i;
return 0;
}
2.设置监视哨的顺序查找
int Search_Seq(SSTable ST,keyType key)
{
ST.R[0].key = key;
for(i=ST.length;ST.R[i].key != key ;i--);
return i;
}
(2)折半查找
<适合对象——只是适用于有序表，且限于顺序存储结构(线性链表无法进行折半查找)>
又称二分查找，对于已经按照一定顺序排列好的列表，每次都用关键字和中间的元素对比，然后判断是在前部分还是后部分还是就是中间的元素，然后继续用关键字和中间的元素对比。
- 设置查找区间初值，low为1，high为表长。
- 当low小于等于high时，循环执行以下操作：
- mid取值为low和high的中间值。
- 将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid。
*若不相等则利用中间位置记录将表对分成前、后两个子表。如果key比中间位置记录的关键字小，则high取为mid-1，否则low为mid+1.
- 循环结束，说明查找区间为空，则查找失败，返回为0。
int Search_Bin(SSTable ST, keyType key)
{
low = 1; high = ST.length; //查找区间的初值
while(low <= high)
{
mid = (low + high) / 2;
if(key == ST.R[mid].key) return mid;
else if(key < ST.R[mid].key) high = mid -1;
else low = mid + 1;
}
return 0;
}
算法分析：
折半查找过程可用二叉树来描述。树中每一个结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。把当前查找区间的中间位置作为根，左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树称为折半查找的判定树。折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度。具有n个结点的判定树的深度为[log2n]+1,所以对于长度为n的有序表，折半查找法在查找成功时和给定值进行比较的关键字个数至多[log2n]+1。
时间复杂度：T(n) =O(log2n)
(3)分块查找
又城索引顺序查找。在此查找法中，除表本身以外，尚需建立一个索引表，对每个子表（或称块）建立索引项，其中包括关键字项（其值为该子表内的最大关键字）和指针项（指示该子表的第一个记录在表中的位置）。索引表按关键字有序，可以使用折半查找或者顺序查找确定关键字所在的子块位置。进入子块后，使用顺序查找查找。
时间复杂度：O(logn)
平均查找长度：设n 个记录的数据集被平均分成m块，每个块中有t 条记录，显然n=mt，或者说m=n/t。再假设Lb为查找索引表的平均查找长度，因最好与最差的等概率原则，所以Lb的平均查找长度为(m+1)/2。 Lw为块中查找记录的平均查找长度，同理可知它的平均查找长度为(t+1)/2。这样分块索引查找的平均查找长度为：
由此可知，平均长度不仅仅取决于数据集的总记录数n，还和每一个块的记录个数t相关。 最佳的情况就是分的块数m与块中的记录数t相同，此时意味着n=mt=t^2。即
可见，分块索引的效率比顺序查找的O(n)是高了不少，不过显然与折半查找的O(logn)相比还有不小的差距。因此在确定所在块的过程中，由于块间有序，所以可以应用折半等手段来提高效率。
