集合：数据元素同属一个集合，具有关键字值（键值）key，数据元素之间没有逻辑关系，集合两大核心操作是查找和排序

查找表：用于查找的数据结构，分为静态查找表和动态查找表，静态查找表的数据元素个数和值都不变，动态查找表支持元素的插入、删除

查找：确定具有特定键值的数据元素在查找表中是否存在，可分为内部查找和外部查找，内部查找的性能通过平均查找长度(ASL)评估，外部查找性能通过访问外存速度评估

静态查找表通常用数组来实现，第0个下标变量存放待查找的元素，查找成功返回下标，查找失败返回0

无序表的查找方法：顺序查找，设置哨兵，从最后一个元素往前查找，时间复杂度O(n),ASL=(n+1)/2

有序表的查找方法：①顺序查找（利用有序性），时间复杂度O(n);②二分查找，时间复杂度O（logn）；③插值查找(二分查找延伸，通过公式计算下一查找位置)，要求数据分布比较均匀；④分块查找（索引查找），对查找表分块建立索引表。查找分两步：查找索引和查找块，n个元素分为m块，时间复杂度ASL=1/2（m+n/m）+1，当m=sqrt（n）时，查找效率最高,时间复杂度为O（根号n）

用查字典类比：
通过查找单词structure，首先通过A-Z索引，找到S块，接着进行块内查找，估计一下t应该在靠后的位置[二分查找/插值查找]，往后翻字典，找到st后，使用顺序查找一个一个比较直到找到单词[顺序查找]。

STL中algorithm头文件包含两个查找元素，find，顺序查找，返回迭代器；binary_search,二分查找，返回布尔类型