272折半查找(二分法查找) 思想:先确定待査找记录所在的范围,然后逐步缩小范 围,直到找到或确认找不到该记录为止。 前提:必须在具有顺序存储结构的有序表中进行。 分三种情况 1)若中间项的值等于x则说明已查到。 2)若x小于中间项的值,则在线性表的前半部分查找 3)若x大于中间项的值,则在线性表的后半部分查找 特点:比顺序查找方法效率高。最坏的情况下,需要比 较|og2n次2.7.2 折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范 围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比 较 log2n次