272折半查找(二分法查找) 思想:先确定待査找记录所在的范围,然后逐步缩小范 围,直到找到或确认找不到该记录为止。 前提:必须在具有顺序存储结构的有序表中进行。 分三种情况 1)若中间项的值等于x则说明已查到。 2)若x小于中间项的值,则在线性表的前半部分查找 3)若x大于中间项的值,则在线性表的后半部分查找 特点:比顺序查找方法效率高。最坏的情况下,需要比 较|og2n次
2.7.2 折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范 围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比 较 log2n次
查找23和79的过程如下图:mid=(ow+high)2不进位取整 (08,14,23,37,46,55,68,79,91) (08,14,23,37,46,55,68,79,91) mid I high (08,14,23,37,46,55,68,79,91) mI high=mid-1 (08,14,23,37,46,55,68,79,91) low=mid+1 high mid (08,14,23,37,46,55,68,79,91) mid Ow high (08,14,23,37,46,55,68,79,91) Ow m d high (08 4,23,37,46,55,68,79 91) low high mid
查找23和79的过程如下图： mid=(low+high)/2不进位取整 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high=mid-1 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low=mid+1 high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid