数据结构-第七章（2.线性结构）

1.顺序查找

1.1知识总览

1.2基本概念

注：以下所有的查找，都按照基本概念（算法思想）、算法实现、优化、和时间复杂度进行叙述。

基本概念：顺序查找又称线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素：对于链表，可通过指针next来依次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和按关键字有序的线性表的顺序查找。

1.3一般线性表的顺序查找

1.4有序线性表的顺序查找

 1.5王道的过程讲解

1.最开始又下面引入：

2.又引入哨兵：（相当于从最末端开始查找，数据从1开始存）

3.最后优化

附：对优化的举例补充

2.折半查找

 2.1知识总览

2.2基本概念

 折半查找又称二分查找，仅适用于有序的顺序表。（想想，如果是无序就没有意义了）

注意从基本原理入手，三个相当于指针的位置（low、mid、high）

后面补充，其详细一步一步的过程。建议如果忘了直接看课件，不会的话再看视频。（应该好理解，就是出现下面的情况-low>high，就查找失败）

 2.3判定树

折半查找的过程可以用下图所示的二叉树来描述，称为判定树。树中非终端结点都是代表能查找成功的记录，树中叶子结点代表查找不成功的情况。它满足下列条件： 

1.查找成功时的比较次数为从该结点到根结点的路径长度与该结点进行的一次比较之和。

2.查找失败时的比较次数为从该结点到根结点的路径长度。

3.若有序序列有n个元素，对应有n个非终端结点和n+1个叶子结点。

4.每个结点的值都大于其左孩子结点的值，小于其右孩子结点的值。

注：下面是落晴学长总结的（自己在二轮刷的时候，再回顾其思想）

上图这个判定树找中间值的操作是 (low+high)/2,它在有偶数个记录时中间值会落到靠左的位置。所以上图我们在{7,10}中选择了7，并且10成为了7的右孩子结点。

事实上我们可以这样取中间值⌈(low+high)/2⌉，符号内为浮点数，这样它在有偶数个记录时中间值会落到靠右位置，此时判定树如下图：

因此，得到规律：

• 若mid=⌈(low+high)/2⌉时，对于任意一个结点，必有左子树结点数-右子树结点数=0或1.
• 若mid=⌊(low+high)/2⌋时，对于任意一个结点，必有右子树结点数-左子树结点数=0或1.
• 对于给定有序表，其判定树的树形只有两种情况(代码不同)，当代码明确时，二分查找的判定树唯一。

2.4查找效率

举例：

2.5常考结论

附：因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排序。 

 3.分块查找

3.1知识总览

3.2基本过程

3.2王道顺序

重点：块内无序，块间有序（这个是本质，也是原则）

折半查找索引 

3.3常考结论（以及二次巩固）