顺序查找和折半查找

顺序查找和折半查找

• 折半查找判定树是一棵二叉排序树，其中序序列是一个有序序列。

  • 可在树结点上一次填上相应的序号，符合折半查找规则

• 折半查找可以通过画出折半查找树来进行查找成功和失败 的平均ASL的计算

  • 可以让最小的分支高度对应于最小的比较次数，最大的分支高度对应于最多的比较次数

• 折半查找的性能分析可以用二叉判定树来衡量，平均查找长度和最大查找长度都是 O（log2n）;

  • 二叉排序树的查找性能与数据的输入顺序有关，最好情况下的平均查找长度与折半查找相同，但
    • 最坏情况即形成单支树时，其查找长度为O（n）。