所谓查找，就是给定一个关键字，找到一个下标，使得给定表中的下标对应元素的关键字等于给定的关键字。

静态查找表

结构如下:

1
2
3
4
5
//顺序查找表的静态存储结构
typedef struct{
    ElemType* elem;//数据中元素的基址，0号单元留空，即下标从1开始
    int length;    //顺序表长度
}SSTable;

顺序表的查找

从后往前查找，如果找不到，就把留空的第一个元素（下标为0）置为待查找的元素。

1
2
3
4
5
int Search_Bin(SSTable ST,KeyType key){
    ST[0].key=key;
    for(int i=ST.length;!EQ(ST[i].key,ley);--i);//从后往前找
    return i;
}

平均查找长度$ASL=\dfrac{n+1}{2}$

折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//传入参数是关键字，返回是下标
int Search_Bin(SSTable ST,KeyType key){
    int low=1;
    int high=ST.length;
    while(low<=high){ //跳出来的条件是严格不等
        int mid=(low+high)/2; //向下取整
        if(EQ(key,ST[mid].key)) {
            return mid;
        }else if(LT(key,ST[mid].key)){
            high=mid-1;            
        }else{
            low=mid+1;
        }
    }
    return 0;
}

平均查找长度$ASL=\dfrac{n+1}{n}\log_2(n+1)-1$