折半查找算法3-3 bin search item, n, key int *item, n, key: t int left, right, mid; left=0; right=n-1 while(left≤ right) nutt mid =( left right)/2 if key item[mid] right= mid-1 else if (key> item [mid]) left= mid +1 else{ printf(“ Successful search n”); return mid 上一页 停止放映 页 printf(“ Search failure\n”) return -1 第16页
下一页 上一页 停止放映 第 16 页 折半查找算法3-3 bin_search ( item , n ,key ) int *item, n, key; { int left ,right , mid; left=0; right = n-1; while ( left right ) { num++; mid = ( left + right )/2 ; if ( key < item[mid]) right = mid - 1; else if (key > item[mid]) left = mid + 1; else{ printf ( “ Successful search\n”); return mid ; } } printf( “ Search failure \n”); return -1; }
折半查找算法3-3主程序 # define“ stdio.h” int num main I int res, key ints[10]={1,2,3,4,5,6,7,8,9,10,11,12}; res=b search(s, 12, 11) printf( res=%d, num=%d\n", res, num) 上一页 停止放映 页 第17页
下一页 上一页 停止放映 第 17 页 折半查找算法3-3主程序 #define “stdio.h” int num; main( ) { int res, key ; int s[10]={1,2,3,4,5,6,7,8,9,10,11,12}; res=b_search(s,12,11); printf("res=%d , num=%d\n",res,num); }
算法讨论 优点:ASL≤10g2n;即每经过一次比较,查找范围 就缩小一半。经log2n次计较就可以完成查找过 程。 ●缺点:因要求有序,所以对所有数据元素按大小 排序是非常费时的操作。另外,顺序存储结构的 插入、删除操作不大便利。 老虑: 能否一次比较抛弃更多的部分(即一次比较, 使查找范围缩得更小),以达到提高效率的目 上一页 的 停止放映 把两种方法(顺序查找和二分查找)结合起来, 来达到提高效率的目的。 页 第18页
下一页 上一页 停止放映 第 18 页 算法讨论 ⚫ 优点: ASL log2n;即每经过一次比较,查找范围 就缩小一半。经log2n 次计较就可以完成查找过 程。 ⚫ 缺点：因要求有序，所以对所有数据元素按大小 排序是非常费时的操作。另外，顺序存储结构的 插入、删除操作不大便利。 ⚫ 考虑： –能否一次比较抛弃更多的部分（即一次比较， 使查找范围缩得更小），以达到提高效率的目 的； –把两种方法（顺序查找和二分查找）结合起来， 来达到提高效率的目的
3、分块查找 ●分块查找又称索引顺序查找,这 是顺序查找的一种改进方法。 ●方法描述:将n个数据元素“按块 有序”划分为m块(m≤n)。每 块中的结点不必有序,但块与 块之间必须“按块有序”;即第1 快中任一元素的关键字都必须小 于第2块中任一元素的关键字;而 上一页 第2块中任一元素又都必须小于第 停止放映 3块中的任一元素, 口■■■■ 每个块 页 中元素不一定是有序的。 第19页
下一页 上一页 停止放映 第 19 页 3、分块查找 ⚫ 分块查找又称索引顺序查找，这 是顺序查找的一种改进方法。 ⚫ 方法描述：将n个数据元素“按块 有序”划分为m块（m n）。每 一块中的结点不必有序，但块与 块之间必须“按块有序”；即第1 快中任一元素的关键字都必须小 于第2块中任一元素的关键字；而 第2块中任一元素又都必须小于第 3块中的任一元素，……。每个块 中元素不一定是有序的