数据结构与算法

查找大观

  • 线性查找

    • 顺序查找
    • 折半查找
      1. 一般用闭区间 [l..r], 中点下标 m = (l + r) / 2
      2. 判定树
        • 节点 = 查找成功，判定数
        • 叶子 = 查找失败，判定区间
    • 分块查找 = 块间有序折半，块内无序顺序

  • 树形查找

  • 散列查找

  • 查找效率

折半查找

  1. 迭代是 [l, m-1] 不是 [l, m]
  2. 中点选取可以 $\lceil \frac{l+r}{2} \rceil$ 也可以 $\lfloor \frac{l+r}{2} \rfloor$ 但是必须统一，所以查找树要么总是|左子树| = |右子树| + 0/1 要么总是 = |右子树| - 0/1
  3. 元素非等概率时，ASL 不一定小于顺序查找！！