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

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

int binary_search(int search_table[], int length, int key)
{
    int low = 0;
    int high = length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key == search_table[mid])
            return mid;
        else if (key < search_table[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

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

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

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

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

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

int seq_search(int search_table[], int length, int key)
{
    int i;
    search_table[0] = key;
    for (i = length; key != search_table[i]; --i);
    return i;
}

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