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

来源： 作者： 出处：巧巧读书 2006-04-28 进入讨论组

• 关 键 词：
• 数据结构

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

教学重点： 折半查找

教学难点： 折半查找

授课内容：

一、折半查找的查找过程

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

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

• 数据结构教程 第二课 抽
• 数据结构教程 第九课 循
• 数据结构教程 第三课 算
• 数据结构教程 第十课 栈
• 数据结构教程 第六课 线
• 数据结构教程 第八课 线
• 数据结构教程 第四课 算
• 数据结构教程 第三十四课&nbs
• 数据结构教程 第三十二课&nbs
• 数据结构教程 第七课 实

二、折半查找的查找实现

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;

三、折半查找的性能分析

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

URL查看 http://www.qqread.com/data-structure/u780104102.html 更多内容请看数据结构、ASP.NET教程、FreeBSD使用教程专题，或进入讨论组讨论。

【收藏此文】【大 中 小】【打印】【关闭】

较早的文章：数据结构教程 第三十一课 动态查找表

较新的文章：数据结构教程 第二十八课 图的存储结构