例:查找21 234567891011 15192134566375808995 ↑ ↑mid ↑up L(1+112 1234567891011 515192134566375808995 个lw↑mid↑up L(1+5)/2上3 1234567891011 515192134566375808995 low↑↑mid↑up L(45)2上4
5 15 19 21 34 56 63 75 80 89 95 1 2 3 4 5 6 7 8 9 10 11 例：查找21 ↑low ↑mid ↑up (1+11)/2=6 5 15 19 21 34 56 63 75 80 89 95 1 2 3 4 5 6 7 8 9 10 11 ↑low ↑mid (1+5)/2=3 ↑up 5 15 19 21 34 56 63 75 80 89 95 1 2 3 4 5 6 7 8 9 10 11 low ↑↑mid (4+5)/2=4 ↑up
例:查找83 1234567891011 151921345663 75 808995 个lw↑mid↑up L(7+1129 1234567891011 51519 21 34566375808995 low↑mid↑up L( 10+1/2上10 1234567891011 515192134566375808995 up↑↑low Up<ow查找 失败
5 15 19 21 34 56 63 75 80 89 95 1 2 3 4 5 6 7 8 9 10 11 例：查找83 ↑low ↑mid ↑up (7+11)/2=9 5 15 19 21 34 56 63 75 80 89 95 1 2 3 4 5 6 7 8 9 10 11 low↑↑mid (10+11)/2=10 ↑up 5 15 19 21 34 56 63 75 80 89 95 1 2 3 4 5 6 7 8 9 10 11 up ↑ ↑ low Up <low 查找 失败
二分查找的算法用C+语言描述如下 int binst( recordfile r,intK,intn)∥二分查找 intk=1,u=n,m;∥置区间初值 while(=u {m=(lHu)/2; if(K>r|m]key)l=m+1;∥/修改下界I值 else ift(K<rm]key)u=m-1;∥修改上界u值 else return m;∥查找成功 return0;∥脱离whle,则u查找不成功
int bins(recordfile r, int K, int n) //二分查找 { int l=1,u=n,m; // 置区间初值 while(l<=u) { m=(l+u)/2; if(K>r[m].key) l=m+1; // 修改下界 l 值 else if(K<r[m].key) u=m-1; // 修改上界u值 else return m; // 查找成功 } return 0; // 脱离while,则 l>u 查找不成功 } 二分查找的算法用C++语言描述如下
算法查找的性能 判定树:描述查找过程的二叉树叫判定树。有n个结点 的判定树的深度为log2nH+1;二分查找成功时比较次 数最多不超过树的深度;二分查找在查找不成功时和关 键字比较的次数最多不超过Log2n+1: 二分查找的ASL 表的长度为:n=2h-l(h=og2(m+1)) 每个元素的查找概率相等P=1/n 平均查找长度: ASLb=∑PC1=∑12= n+log2m+1
判定树：描述查找过程的二叉树叫判定树。有n个结点 的判定树的深度为log2n+1 ； 二分查找成功时比较次 数最多不超过树的深度 ；二分查找在查找不成功时和关 键字比较的次数最多不超过 log2n +1； 算法查找的性能 二分查找的ASL 表的长度为：n=2h -1(h=log2(n+1)) 每个元素的查找概率相等Pi=1/n 平均查找长度 :
算法的评价 二分查找的效率比顺序查找高,但二分查找只能适用于 有序表,且存储结构仅限于向量(对线性链表无法进行 折半查找),当表经常需要插入或删除一个元素时,就 需要来回移动元素。因此,折半查找方法适用于不经常 变动而査找频繁的有序列表
二分查找的效率比顺序查找高，但二分查找只能适用于 有序表，且存储结构仅限于向量（对线性链表无法进行 折半查找），当表经常需要插入或删除一个元素时，就 需要来回移动元素。因此，折半查找方法适用于不经常 变动而查找频繁的有序列表。 算法的评价