1.与查找相关的概念
1.1：查找表
1.2：关键字
1.3：平均查找长度ASL
2.线性表的查找
2.1：顺序查找
在顺序查找中：下标 为0 的位置，通常不存储有效数据，专门用来放哨兵。(有效数据从下标为1的位置开始存储)
代码（优化前：不带哨兵的顺序查找）
// 定义查找表的数据结构（顺序表）typedefstruct{ElemType*elem;// 动态数组起始地址：实际申请 TableLen+1 个空间// 有效数据存在 elem[1]、elem[2]....TableLen]。elem[0] 存哨兵位intTableLen;// 表的有效长度：表示有效数据的个数}SSTable;// ============ 版本一：无哨兵 ============// 找到则返回该元素的下标，找不到返回0intSearch_Seq(SSTable ST,ElemType key){// 从表尾 TableLen 往前找，没有哨兵，for循环必须同时判断两个条件inti;for(i=ST.TableLen;i>=1&&ST.elem[i]!=key;--i);// i>=1 说明正常找到；i==0 说明遍历完都没找到// 注：i 最多减到0就停，不会访问 elem[0]（那是哨兵位，未存有效数据）returni;}代码（优化后：带哨兵的顺序查找）
// 定义查找表的数据结构（顺序表）typedefstruct{ElemType*elem;// 动态数组起始地址：实际申请 TableLen+1 个空间// 有效数据存在 elem[1]、elem[2]....TableLen]，另外，elem[0] 存储哨兵位intTableLen;// 表的有效长度：表示有效数据的个数}SSTable;// ============ 版本二：带哨兵 ============// 找到则返回该元素的下标，找不到返回0intSearch_Seq(SSTable ST,ElemType key){// 【哨兵设置】把 key 存进 elem[0]——正是为它预留的哨兵位// 目的：避免循环中反复判断下标是否越界，简化循环条件ST.elem[0]=key;// 【从后往前遍历查找】// 从表尾（下标 TableLen，最后一个有效数据）向前找// 因有哨兵，即使遍历到表头也必然匹配 key，循环必停，不会越界inti;// ★ i 在循环外声明，供 return 使用for(i=ST.TableLen;ST.elem[i]!=key;--i);// 【返回结果】// i 不为0：找到，返回下标；i==0：命中哨兵，表中不存在目标元素，查找失败returni;}顺序查找的平均查找长度
元素有序的顺序表、元素无序的顺序表的对比
2.2：折半查找
代码：
// 定义数据元素类型typedefintElemType;// 定义查找表的数据结构（顺序表）typedefstruct{ElemType*elem;// 动态数组基址：指向存储数据的数组首地址intTableLen;// 表的长度：表示顺序表中有效元素的个数}SSTable;/********************************************************** 函数功能：折半查找（二分查找） 前提条件：顺序表必须有序（升序） 参数：ST 顺序表结构体 key 要查找的关键字 返回值：找到返回下标，找不到返回 -1 **********************************************************/intBinarySearch(SSTable ST,ElemType key){// 左边界：初始指向第一个元素intleft=0;// 右边界：初始指向最后一个元素intright=ST.TableLen-1;intmid;// 区间有效时继续查找while(left<=right){// 计算中间位置mid=(left+right)/2;// 找到目标，返回下标if(ST.elem[mid]==key){returnmid;}// key 更小，去左半区elseif(key<ST.elem[mid]){right=mid-1;}// key 更大，去右半区else{left=mid+1;}}//当left>right时，表示查找失败，返回-1return-1;}
