查找
1. 一些基本概念
关键字：能唯一标识该元素
查找：给定值k，在含n个元素的表中找出关键字==k的元素。找到返回其位置信息，否则返回-1。
动、静态查找表：查找同时对表进行修改（插入、删除等），相应的表为动态，否则为静态。
内、外查找：整个查找过程在内存中进行，称之为内查找；需要访问外存，则为外查找。
平均查找长度ASL：∑pici，pi：查找第i个元素的概率，一般为1/n，ci：找到第i个元素所需进行的关键字的比较次数。
2. 怎样评价一个查找算法？
答：通过平均查找长度ASL。其数量级反应了查找算法的时间复杂度。
顺序表的查找
3. 顺序查找
答：
基本思想：从表的一端开始顺序扫描顺序表，依次扫描到的元素关键字与k比较，若找到，查找成功；若扫描结束也未找到，则失败。
时间复杂度：O（n）
优点：算法简单，且对表的结构无任何要求。
缺点：查找效率低。
4. 折半查找
答：要求线性表是有序表。不适合链式存储结构的数据查找。
基本思想：在[low, high]之间查找目标关键字，每次检查mid=(low+high)/2，根据mid所指元素与目标关键字的大小调整low和high，不断缩小low和high的范围，当low>high时则查找失败。
判定树（或判定表）构造及特性：
构造：由mid所指元素将原有元素分割到左右子树中。
特性：① 折半查找的判定树是是平衡的二叉排序树（左<中<右）
② 只有最下面一层试不满的
③ 若查找表有n个关键字，则失败结点有n+1个
④ 树高h=log2(n+1)上取整，不包含失败结点
时间复杂度：O（log2n）
优点：查找效率高文章来源：https://uudwc.com/A/19owd
缺文章来源地址https://uudwc.com/A/19owd
