基本概念

定义：在数据结构中寻找满足某种条件的数据元素的过程，查找成功与查找失败。

查找表：用于查找的数据集合，由同一种数据类型（或记录）的组成，可以是一个数组或链表等数据类型。

操作：

查询某个特定的数据元素是否在查找表中
检索满足条件的某个特定的数据元素的各种属性
在查找表中插入一个元素
从查找表中删除一个元素

前两种：静态查找表；前四个：动态查找表

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

平均查找长度：查找时，关键字比较次数的平均值——$ASL=\sum_{i=1}^nP_iC_i$

顺序查找

最简单，最好理解。从头开始进行比较。

也称为线性查找（可以有序，也可以无序），主要用于在线性表中进行查找。

无序线性表的顺序查找

无序线性表进行顺序查找，查找失败时要遍历整个线性表

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;

int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0]=key;		// 哨兵
    for(int i=ST.TableLen;ST.elem[i]!=key;--i)
        return i;
}

平均查找长度：

$ASL_{success}=\sum_{i=1}^n P_iC_i=\sum_{i=1}^nP_i(n-i+1)=\sum_{i=1}^n\frac{1}{n}*(n-i+1)=\frac{n+1}{2}$

$ASL_{failed}=\sum_{i=1}^nP_iC_i=\sum_{i=1}^n\frac{1}{n}*(n+1)=n+1$

有序线性表的顺序查找

对关键字有序线性表进行顺序查找，查找失败不一定要遍历整个线性表，遍历到比它大的元素就可以

判定树：描述查找过程的二叉排序树

平均查找长度：$n+1$个失败节点

$ASL_{failed}=\sum_{i=1}^nP_iC_i=\sum_{i=1}^n\frac{1}{n+1}=\frac{1+2+…+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$

折半查找（二分查找）

仅适用于有序表的顺序表——数组

思想：

首先将给定值key与表中中间位置的元素进行比较
若相等，就返回该元素的位置
若不等，则在前半部分或后半部分进行查找

查找升序序列时：

若key小于中间元素，则查找前半部分
若key大于中间元素，则查找后半部分

重复该过程，直到查找到元素为止；或者查找失败

int Binary_Search(SeqList L, ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            low=mid+1l
    }
    return -1;
}