9.7.3　二分查找

二分查找（Binary Search），又称折半查找。必须满足两个前提：

·存储结构必须是顺序存储；

·关键码必须有序排列。

在符号表中取中间记录作为比较对象，若中间值和给定值相等，则查找成功；若给定值小于中间值，则在左半区继续查找，否则在右半区进行查找；不断重复直到成功或失败。如图在含有10个数据元素的有序表中查找37的过程，如图9-47所示。

图9-47　二分法查找过程

在查找表中各个关键字被查找概率相同的情况下，折半查找的平均查找长度为：ASL=log2（n+1）-1，所以时间复杂度为O（log n）