数据结构复习资料
3.二分查找的性能分析 为了分析二分查找的性能，可以用二叉树来描述二分查找 过程。把当前查找区间的中点作为根结点，左子区间和右 子区间分别作为根的左子树和右子树，左子区间和右子区 间再按类似的方法，由此得到的二叉树称为二分查找的判 定 树 。 例 如 ， 图 8-1 给 定 的 关 键 字 序 列 05,13,19,21,37,56,64,74,80,88,92,的判定树见图8-3。5 2 8
0 1
3
6
9
4
7
10
图 8-3 具有 11 个关键字序列的二分查找判定树