折半查找，亦称二分查找，是线性表查找中效率最高的经典算法。教材给出的标准定义是：折半查找仅适用于采用顺序存储结构且按关键字有序排列的线性表，其基本思想是将给定值与中间位置记录的关键字进行比较，若相等则查找成功，若不相等则根据比较结果将查找区间缩小为前半部分或后半部分，直至查找成功或区间为空。这一定义中包含两个必须同时满足的前提条件：其一，存储结构必须是顺序存储，也就是用数组实现；其二，表中记录必须按关键字有序。两个条件缺一不可，命题人恰恰喜欢在这两个前提上做文章。
与折半查找同属查找技术范畴的还有二叉排序树。二叉排序树又称二叉查找树或二叉搜索树，其递归定义是：二叉排序树或者是一棵空树，或者是一棵满足如下性质的二叉树，若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；左右子树本身也分别是一棵二叉排序树。由这一定义可以立即导出一条极为重要的性质：对二叉排序树进行中序遍历，可以得到一个按关键字递增的有序序列。这一性质是二叉排序树的立身之本，也是考试中判断一棵二叉树是否为二叉排序树的最快方法。
平衡二叉树是在二叉排序树基础上提出的强化结构，教材中常称为平衡二叉排序树或AVL树。其定义是：平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树，它的左子树与右子树的高度之差的绝对值不超过一，且左子树与右子树也都是平衡二叉树。定义中引入了平衡因子的概念，平衡因子等于结点左子树高度减去右子树高度，所有结点的平衡因子只能取负一、零、正一三个值。一旦某个结点的平衡因子绝对值达到二，这棵树就失衡了，必须通过旋转操作恢复平衡。
从数据结构演进的角度看，顺序查找、折半查找与树形查找构成查找技术的三个层次。顺序查找对存储结构和数据排列没有任何要求，适用性最广但平均比较次数最多；折半查找通过有序性与顺序存储两个约束换来了对数级别的效率；二叉排序树则打破了顺序存储的约束，用链表结构支持动态插入删除的同时保持了接近折半查找的效率。理解这三个层次的约束条件与效率代价的对应关系，是学好查找技术的认知框架。
考生常把折半查找、二叉排序树、平衡二叉树三者混为一谈。折半查找是一种算法，作用于有序数组，静态数据场景下效率最优；二叉排序树是一种数据结构，作用于动态数据集，支持高效的插入与删除；平衡二叉树是二叉排序树的性能保障版本，解决的是二叉排序树在特定插入序列下退化成单链的问题。算法、结构、结构的优化版本，三者层次不同，命题人常常把三者放在一道题里相互干扰。
折半查找每次比较都能把查找区间一分为二，这是其效率的根本来源。设有序表中有n个元素，第一次比较后查找范围缩小为最多二分之n个，第二次比较后缩小为最多四分之n个，经过k次比较后范围缩小为n除以二的k次方。当范围缩小到一仍不匹配时查找失败，因此最坏情况下比较次数k满足二的k减一次方小于n小于等于二的k次方，即k等于log2n向上取整再加一，或者等价地描述为判定树的深度。若n恰好为二的某次方减一，最坏比较次数为log2(n+1)。平均情况下，成功查找的期望比较次数约为log2(n+1)减一，当n足够大时，平均查找长度与n的对数同阶。这一效率远优于顺序查找的平均二分之n次比较，也正是折半查找被称为查找技术经典算法的原因。
折半查找的比较过程可以画成一棵二叉判定树。判定树的根结点是第一次比较的中间位置元素，左子树对应前半区间继续折半的结果，右子树对应后半区间。由于每次划分都取中间位置，判定树的结构近似于一棵完全二叉树，深度为log2n向上取整加一。判定树的价值在于把抽象的比较次数问题转化为树的层次问题：查找某个元素需要的比较次数等于该元素在判定树中所处的层数。成功查找的平均查找长度等于各层结点数与层数乘积之和除以结点总数；失败查找的平均查找长度则是各失败结点到根路径长度的加权平均。判定树还是判断题目的有力工具：任何一次折半查找实际走过的比较序列，必须对应判定树上一条自根向下的合法路径，凡是违背路径单调划分规律的序列一定不可能出现。这里可以进一步推导平均查找长度的精确公式。设判定树深度为h，则成功查找的平均查找长度等于从一到h的各层结点数乘以层数之和除以n。当n较大时，判定树接近满二叉树，第j层约有二分之n乘二的一次方个结点，逐层求和后可近似得到平均查找长度约等于log2(n+1)减一。这一近似公式在选择题中可以直接用于快速估算，但遇到精确计算题仍须老老实实分层计数，不能把近似结果当成精确答案。
二叉排序树的查找过程与折半查找同源：从根结点开始，给定值与根比较，相等则命中，小于根则转向左子树，大于根则转向右子树，逐层递归，直至命中或到达空指针。查找长度取决于结点所在层次，而树的高度取决于插入序列。同样的关键字集合，若按递增顺序依次插入，每个新结点都成为前驱的右孩子，树退化为一条右斜单链，高度为n，查找性能退化为顺序查找；若按中序先入的折半顺序插入，树接近完全二叉树形态，高度约log2n。这一退化风险正是平衡二叉树要解决的问题：插入或删除导致某结点平衡因子绝对值达到二时，通过单旋或双旋调整局部结构，使树恢复平衡的同时保持中序有序性不变。
线性表查找技术按适用条件可分为顺序查找、折半查找与分块查找三类。顺序查找无任何前提，逐个比较，平均查找长度约二分之n加一；折半查找要求有序与顺序存储，平均查找长度对数级；分块查找又称索引顺序查找，将表分为若干块，块间有序块内无序，先通过索引确定所在块再在块内顺序查找，其平均查找长度介于顺序查找与折半查找之间。分块查找的定位价值在于：它是唯一兼顾了动态性、较低存储要求与亚线性查找效率的折中方案，适用于数据量大且变动频繁的场景。
二叉排序树支持动态维护。插入操作本质是一次失败的查找：沿查找路径到达空指针位置，将新结点挂在此处，因而新插入的结点永远是叶子。删除操作分三种情形：被删结点是叶子则直接摘除；被删结点只有一棵子树则用子树顶替；被删结点左右子树均不空时，教材标准做法是用其中序前驱或中序后继的值替换被删结点，再删除该前驱或后继结点。删除的第三种情形是计算题与概念题的密集出题区，必须牢记替换的是中序序列中紧邻的结点，这是维持二叉排序树性质的唯一正确途径。构造过程同样值得完整演练：给定一个无序关键字序列，依次执行插入操作，第一个元素成为根，此后每个元素都从根开始比较，小于当前结点走左子树、大于走右子树，到达空位置即落座。同一序列按不同顺序插入，得到的树形可能完全不同，树高也随之改变。例如五个递增的关键字若按中序先入的顺序插入，得到的是高度为三的丰满形态；若直接按递增顺序插入，则得到一条高度为五的右斜链。这一构造演练是理解退化问题最直观的途径。
AVL树的再平衡手段共四种旋转，按失衡结点与插入路径的方向组合命名。在失衡结点的左孩子的左子树上插入导致失衡时执行右单旋，简称LL型；在右孩子的右子树上插入导致失衡时执行左单旋，简称RR型；在左孩子的右子树上插入导致失衡时，先对左孩子执行左旋再对失衡结点执行右旋，称为LR型双旋；在右孩子的左子树上插入导致失衡时，先对右孩子执行右旋再对失衡结点执行左旋，称为RL型双旋。判别口诀为：插入路径的两个方向与失衡结点两侧的组合，同向为单旋，异向为双旋。旋转操作只修改常数个指针，代价极低，却能把高度为log2n量级的性质始终维持住，这是AVL树得以保证最坏情况查找性能的关键。
平衡二叉树只是二叉查找树家族的一员。红黑树放宽了平衡条件，允许最长路径不超过最短路径的两倍，用更少的旋转换取更均衡的插入删除开销，被标准库广泛采用；B树与B+树则是面向外存的平衡多路查找树，通过增大结点出度降低树高，减少磁盘访问次数，是数据库索引的底层结构。软考对查找树的考查以二叉排序树与平衡二叉树为核心，红黑树与B树一般只要求知道基本概念与适用场景。考生建立这一全景定位后，遇到跨结构的选
本篇完！