折半查找

前提：必须是顺序存储且有序。

• 过程：
  • low=1, high=n
  • mid = (low + high) / 2
  • 若 key < a[mid]，则 high = mid - 1
  • 若 key > a[mid]，则 low = mid + 1
• 判定树：折半查找的过程可用二叉树描述。
  • 树高：$\lfloor {\log }_{2}n\rfloor +1$。
  • 查找失败：对应判定树的空指针（外部结点）。
• ASL： $ASL\approx {\log }_2(n+1)-1$