AutoCAD 3DMAX C语言 Pro/E UG JAVA编程 PHP编程 Maya动画 Matlab应用 Android
Photoshop Word Excel flash VB编程 VC编程 Coreldraw SolidWorks A Designer Unity3D
 首页 > 数据结构

数据结构教程 第三十课 静态查找表(二)有序表的查找

51自学网 2015-09-08 http://www.51zixue.net

教学目的: 掌握有序表的折半查找法

教学重点: 折半查找

教学难点: 折半查找

授课内容:

一、折半查找的查找过程

以有序表表示静态查找表时,Search函数可用折半查找来实现。

先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。

二、折半查找的查找实现

int Search_Bin(SSTable ST,KeyType key){

low=1;high=ST.length;

while(low<=high){

mid=(low+high)/2;

if EQ(key,ST.elem[mid].key) return mid;

else if LT(key,ST.elem[mid].key) high=mid -1;

else low=mid +1 ;

}

return 0;

}//Search_Bin;

三、折半查找的性能分析

折半查找在查找成功时和给定值进行比较的关键字个数至多为

 

 

 
上一篇:数据结构教程&nbsp;第二十九课&nbsp;静态查找表(一)顺序表的查找  下一篇:返回列表