折半查找（二分查找）是一种简单而又高效的查找算法，其查找长度至多为㏒₂ⁿ+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》 （中文名《编程珠玑》）。我就是在读那本书的时候，发现了我要找的代码例子：二分查找。
继续阅读 →