折半查找（二分查找）是一种简单而又高效的查找算法，其查找长度至多为㏒₂ⁿ+1（判定树的深度），平均查找长度为㏒₂⁽ⁿ⁺¹⁾-1，效率比顺序查找要高，但折半查找只能适用于顺序存储有序表（如对线性链表就无法有效地进行折半查找）。

折半查找的C/C++代码实现：

这是折半查找的经典实现。不过它还有bug；效率上也还可以再改进。关于bug部分在这里做一部分摘录（如欲详细了解请见《代码之美》，效率改进详见《编程珠玑》）：

每当讨论漂亮的代码，就很容易让人联想起Jon Bentley那本经典的由Addison-Wesley出版的《Programming Pearls》 （中文名《编程珠玑》）。我就是在读那本书的时候，发现了我要找的代码例子：二分查找。
继续阅读 »

顺序查找（Sequential Search）算法简单，适用面广（对查找表结构无任何要求），但其查找效率较低，等概率下平均查找长度为(n+1)/2。

在条件允许情况下，顺序查找可以设置一个监视哨，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。严版《数据结构》说这个改进能使查找长度在≥1000时查找所需平均时间几乎减少一半。

顺序查找的C/C++代码实现：

第4行即为设置监视哨，当然监视哨也可以设在高下标处。

查找表（Search Table）是一种在实际应用中大量使用的数据结构。查找表分为静态查找表和动态查找表，静态查找表只进行查找操作，动态查找表则在查找的同时还进行插入或删除操作。

静态查找表主要是：顺序表、线性链表、索引顺序表等。
动态查找表主要是：二叉排序树、平衡二叉树、B-树、B+树等。

哈希表

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表就叫哈希表。

哈希函数的构造方法：
1. 直接定址法 H(key) = key 或 H(key) = a * key + b
2. 除留余数法 H(key) = key % p, p ≤ length （一般情况下，p为质数或不包含<20的质因数的合数。）
3. 等等…

处理冲突的方法：
1. 开放定址法   (1). 线性探测再散列 (2). 二次探测再散列 (3). 伪随机数探测再散列
2. 链地址法
3. 等等…

哈希表的查找长度：依赖于3个因素，哈希函数、处理冲突的方法和哈希表装填因子。