数据结构：重要的查找算法有哪些？

Question

除了折半查找 还有哪些查找重要
B+-？二叉排序树？平衡二叉树？trie？

另外 堆排序和哈希表查找重要吗？

Answer 1

折半查找也就是二分查找，它必须满足排序关系。
查找也可以用二叉查找树，一般复杂度为O(logn),最坏为O(n)。
也可用平衡树进行查找，如AVL,Treap,Splay等，可以做到保持O(logn)。

比二分查找性能更优的：大概只有Hash了吧。如果Hash函数设计的好，基本可以认为是O(1)

堆排序比较有意思，值得研究一下，理解了后，很有用～，也很重要。