顺序查找算法3-2(改进算法) o seg search adv(item, n, key int米item,n, k ey I int i=0; item[n]=key while( item[i] != key 1++; if (i<n) printf(“查找成功!\n”); return(i);} else 上一页 printf(“查找失败!\n”); return(-1);} 停止放映 页 注:顺序查找算法中,执行频率最高的是 while语 句,改进后,可以节省近一半的时间。 第11页
下一页 上一页 停止放映 第 11 页 顺序查找算法3-2（改进算法） ⚫ seq_search_adv(item , n , key ) int *item ,n , key ; { int i=0 ; item[n]=key ; while ( item[i] != key ) i++; if ( i< n ) { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1); } } 注: 顺序查找算法中,执行频率最高的是while语 句,改进后,可以节省近一半的时间
顺序查找算法主程序 # include“ stdio.h” main t int key, n, loc=0; inta[10]={43,15,21,37,2,5,82} printf("Input key, n: &key, &n) loc=seg search adv(a, n, key) if (loc >0) 上一页 printf("loc=%d, key=%d\n", loc, key) 停止放映 页 第12页
下一页 上一页 停止放映 第 12 页 顺序查找算法主程序 #include “stdio.h” main() ｛ int key,n,loc=0; int a[10]={43,15,21,37,2,5,82}; printf(“Input key,n:”,&key,&n); loc=seq_search_adv(a,n,key); if (loc >0) printf(“loc=%d,key=%d\n”,loc,key); }
算法讨论 ●平均查找长度ASL 在等概率的情况下, ASL=∑Pi米Ci=1∑(n-i+1) n+1 2 般情况下,ASL≤n 优点: 2 对结点的逻辑次序(不必有序)和存储结构(顺序、链 表均可)无要求; 当序列中的记录“基本有序”或Y值较小时,是较好 上一页 的算法; ●缺点: 停止放映 AS较长 页 ●讨论:能否减少比较次数,以提高效率。例如,二分法 等。 第13页
下一页 上一页 停止放映 第 13 页 算法讨论 ⚫ 平均查找长度ASL 在等概率的情况下, ASL = Pi*Ci = (n-i+1) = 一般情况下, ASL ⚫ 优点: –对结点的逻辑次序(不必有序)和存储结构(顺序、链 表均可）无要求； –当序列中的记录“基本有序”或N值较小时，是较好 的算法； ⚫ 缺点： –ASL较长 ⚫ 讨论：能否减少比较次数，以提高效率。例如，二分法 等。 n i=1 n 1 2 n+1 2 n i=1 n
2、折半查找 二分查找是一种高效的查找方法。它可以明显减少比较次 数,提高查找效率。但是,二分查找的先决条件是查找表 中的数据元素必须有序。 算法步骤 step1首先确定整个查找区间的中间位置, mid =( left right )/2 step2用待查关键字值与中间位置的关键字值进行比较; 若相等,则查找成功; 若大于,则在后半区域继续进行二分查找; 若小于,则在前半区域继续进行二分查找。 上一页 对确定的缩小区域再按二分公式,重复上述步骤; 最后,得到结果: 停止放映 要么,查找成功,要么,查找失败。 页 存储结构 用一维数组存放。 第14页
下一页 上一页 停止放映 第 14 页 2、折半查找 ⚫ 二分查找是一种高效的查找方法。它可以明显减少比较次 数，提高查找效率。但是，二分查找的先决条件是查找表 中的数据元素必须有序。 ⚫ 算法步骤： –step1 首先确定整个查找区间的中间位置， mid = （ left + right ）/ 2 –step2 用待查关键字值与中间位置的关键字值进行比较； • 若相等，则查找成功； • 若大于，则在后半区域继续进行二分查找； • 若小于，则在前半区域继续进行二分查找。 –对确定的缩小区域再按二分公式，重复上述步骤； –最后，得到结果： • 要么，查找成功， 要么，查找失败。 ⚫ 存储结构 –用一维数组存放
折半查找算法举例 ●对给定数列(有序){3,5,11,17,21,23, 28,30,32,50},按折半查找算法,查找关键字 值为30的数据元素。 第1次:{3,5,1117,21,23,28,30,32,50} left mid right mid1=(1+10)/2=5 上一页 第2次:{23,28,30,32,50} left mid right 停止放映 mid2=(6+10)2=8 页 第15页
下一页 上一页 停止放映 第 15 页 折半查找算法举例 ⚫ 对给定数列（有序）{ 3，5，11，17，21，23， 28，30，32，50}，按折半查找算法，查找关键字 值为30的数据元素。 第1次： { 3，5，11，17，21，23，28，30，32，50 } mid1= （1+10）/2 = 5 第2次： { 23，28，30，32，50 } mid2 = （6+10） /2 = 8 left right mid left mid right