折半查找算法实现 int Search Bin (TB SL, TYPe key i int low=1, high= SL length, mid while low<=high) mid=(loW+high)∥/2 if(key==SL elem[mid]. key return mid if(key<SLelem[mid]. keyhigh=mid-1 if(key>slelem[mid]. key low=mid+1; return o: 第21页
第 21 页 折半查找算法实现 int Search_Bin(TB SL, TYPE key) { int low = 1, high = SL.length,mid; while(low<=high) { mid=(low+high)/2; if(key==SL.elem[mid].key)return mid; if(key<SL.elem[mid].key)high=mid-1; if(key>SL.elem[mid].key)low=mid+1; } return 0; }
折半查找算法总结 平均查找长度: ASL (1×2+2×2+…+k×2) 查找成功: n+1 og2(n+1) 时间复杂度:O(og2n) 优点:查找效率高; ·缺点:查找结构有限制;插入、删除操作困难。 适用场合:记录按关键字值有序排列,查找结 构为顺序表结构,数据不经常变动(静态査 找) 第22页
折半查找算法总结 • 平均查找长度： 查找成功: 时间复杂度: O(log2n) • 优点：查找效率高； • 缺点：查找结构有限制；插入、删除操作困难。 • 适用场合：记录按关键字值有序排列，查找结 构为顺序表结构，数据不经常变动（静态查 找）。 第 22 页 log (n 1) 1 1 2 + − + = = + + + − n n ASLsucc (1 2 2 2 2 ) 1 0 1 k 1 k n
13二叉排序树查找 若要对动态查找表进行高效率 的查找操作(包含可能的数据删 除或插入操作),可采用二叉推 序树作为查找表的组织形式 第23页
第 23 页 若要对动态查找表进行高效率 的查找操作（包含可能的数据删 除或插入操作），可采用二叉排 序树作为查找表的组织形式。 1.3 二叉排序树查找
二叉排序树的概念 二叉排序树(或二叉查找树)或者是 棵空树;或者是具有如下特性的二叉树 (1)若它的左子树不空,则左子树上 所有结点的值均小于根结点的值; (2)若它的右子树不空,则右子树上 所有结点的值均大于根结点的值; (3)它的左、右子树也都分别是二叉 排序树。 第24页
第 24 页 （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； 二叉排序树（或二叉查找树）或者是一 棵空树；或者是具有如下特性的二叉树： （3）它的左、右子树也都分别是二叉 排序树。 （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； 二叉排序树的概念
50 30 80 20 40 90 10(25(35 45(85 23 88 是二叉排序树 第25页
第 25 页 50 30 80 20 90 10 85 40 25 35 23 88 是二叉排序树 45