41.2折半查找(二分法查找) 思想:先确定待査找记录所在的范围,然后逐步缩小范 围,直到找到或确认找不到该记录为止。 前提:必须在具有顺序存储结构的有序表中进行。 分三种情况 1)若中间项的值等于x则说明已查到。 2)若x小于中间项的值,则在线性表的前半部分查找 3)若x大于中间项的值,则在线性表的后半部分查找 特点:比顺序查找方法效率高。最坏的情况下,需要比 较|og2n次
4.1.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 high 23 6,55,68,79,91) high=mid-1 (08,14,23,37,46,55,68,79,91) low=mid+1 high d (08,14,23,37,46,55,68,79,91) mid Ow high (08,14,23,37,46,55,68,79,91) low mid high (08,14,23, 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
折半查找的c语言算法程序: int Search Bin( SSTable Sti, int n, int key Rint low, high, mid; low=l: high=n: while(low<=high) i mid=(lowthigh)/2; if( TIMid. key==key) return(mid;查找成功 else if((key< TIMid]. key)high=mid-1;/在前半区间继续查找* else ow=mid+l /在后半区间继续查找* return(O); 查找不成功*
折半查找的c语言算法程序： int Search_Bin( SSTable ST[ ], int n, int key) {int low, high,mid; low=1; high=n; while(low<=high) { mid=(low+high)/2; if(ST[mid].key= = key) return (mid); /*查找成功*/ else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找*/ else low=mid+1; /*在后半区间继续查找*/ } return (0); /*查找不成功*/ }
41.3分块查找(索引顺序查找) 是顺序查找的一种改进方法,就是把被查找的表 分成若干块,每块中记录的存放顺序是无序的,但块 与块之间必须按关键字有序。即第一块中任一记录的 关键字都小于第二块中任一记录的关键字,而第二块 中任一记录的关键字都小于第三块中任一记录的关键 字,依此类推。 该法要为被查找的表建立一个索引表,索引表中 的一项对应于表中的一块,索引表中含有这一块中的 最大关键字和指向块内第一个记录位置的指针,索引 表中各项关键字有序
是顺序查找的一种改进方法，就是把被查找的表 分成若干块，每块中记录的存放顺序是无序的，但块 与块之间必须按关键字有序。即第一块中任一记录的 关键字都小于第二块中任一记录的关键字，而第二块 中任一记录的关键字都小于第三块中任一记录的关键 字，依此类推。 该法要为被查找的表建立一个索引表，索引表中 的一项对应于表中的一块，索引表中含有这一块中的 最大关键字和指向块内第一个记录位置的指针，索引 表中各项关键字有序。 4.1.3分块查找（索引顺序查找）