查找算法	平均时间复杂度	空间复杂度	查找条件
顺序查找	O(n)	O(1)	无序/有序
二分查找	O(log2n)	O(1)	有序
二叉排序树	O(log2n)~O(n)
平衡二叉树	O(log2n)
红黑树	O(log2n)
哈希查找	O(1)	O(n)	无序/有序
2-3树	O(log2n-log3n)
B树/B+树	O(log2n)

查找技术(内存)

线性表的查找技术

顺序查找(sequential search)

二分查找(binary search)

lower_bound

对于给定的一个值,在一个排序后的区间中找到第一个这样的位置,使得将这个值插入到这个位置前面时,不会破坏顺序

auto i = lower_bound(a.begin(), a.end(), 1);
cout << *i << endl;

upper_bound

对于给定的一个值,在一个排序后的区间中找到最后一个这样的位置,使得将这个值插入到这个位置前面时,不会破环顺序

auto i = upper_bound(a.begin(), a.end(), 2);
cout << *i << endl;

equal_range

对于给定的一个值,在一个排序后的区间中找到一个最大的区间,使得将这个值插入其中的任何位置,都不会破坏顺序

auto j = equal_range(a.begin(), a.end(), 3);
cout << *(j.first) << ' ' << *(j.second) << endl;

binary_search

如果排序后的区间中包含了与给定的值相同的值,则返回true,否则返回false

binary_search(a.begin(), a.end(), 4);

树表的查找技术

二叉排序树(binary sort tree)

左子树<结点<右子树

• 中序遍历

平衡二叉树(balance binary tree)

AVL树 -> |左子树深度-右子树深度| <= 1

• 整体平衡

红黑树(red-black tree)

• 局部平衡

散列表的查找技术

索引技术(文件系统/数据库系统)

线性索引

树形索引

2-3树(2-3 tree)

• 一个结点包含一个或者两个关键码
• 每个内部结点有2个子女(包含一个关键码)或者3个子女(包含两个关键码)
• 所有叶子结点都在树的同一层

B树(B-tree)

一种平衡的多路查找树,主要面向动态查找,通常用在文件系统中

B+树(B+tree)

• 终端结点存储记录(关键码和指向实际记录的指针),内部结点存储关键码(用于引导查找)
• 终端结点链接成链表,通过访问链表中的所有终端结点,就可以按照排序的顺序遍历全部记录
• select