例如:在关键字有序序列 2,4,7,9,10,14,18,26,32,40)中采用二分查 找法査找V=7的元素。查找过程如下开始: 2479101418263240 high=10 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 例如：在关键字有序序列 〔2,4,7,9,10,14,18,26,32,40〕中采用二分查 找法查找V=7的元素。查找过程如下开始： 2 4 7 9 10 14 18 26 32 40 Low＝1 high＝10
第一次比较:mid=(1+10)/2取整)=5 2479 101418263240 Low=lhigh=4 mid=5 注:右端点左移 第二次比较:mid=(1+4)2取整)=2 2 101418263240 「high=4 性注:左端点右移 Mid=2 第三次比较:mid=(2+4)/2取整)=3 101418263240 「m=3high=4 查找完成 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 第一次比较：mid＝（1+10)/2取整）＝5 2 4 7 9 10 14 18 26 32 40 Low＝1 high＝4 mid＝5 注：右端点左移 第二次比较：mid＝（1+4)/2取整）＝2 2 4 7 9 10 14 18 26 32 40 mid＝3 Low＝3 Low＝1 Mid＝2 第三次比较：mid＝（2+4)/2取整）＝3 2 4 7 9 10 14 18 26 32 40 注：左端点右移 查找完成 high＝4 high＝4
3、二分查找算法 int Bin Search(seqlist r, Key Type K) {在有序表R中进行二分查找,成功时返回结点的位置,失败时返回零 int low=1,high-n,mid;〃置当前查找区间上、下界的初值 while(low<=high)i ∥当前查找区间R[ow.high非空 mid=(low+high)/2 if(R[mid]key==K) return mid;查找成功返回 if(r[mid]. kdy>k) high=mid-1;∥继续在Rlow.mid-1中查找 low=mid+1;/继续在Rmd+1high中查找/ return0;∥当ow>high时表示查找区间为空,查找失败 //BinSearch 二分查找算法亦很容易给出其递归程序【参见练习】 系
武汉理工大学华夏学院-信息工程 系 int BinSearch(SeqList R，KeyType K) {//在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零 int low=1，high=n，mid； //置当前查找区间上、下界的初值 while(low<=high){ //当前查找区间R[low..high]非空 mid=(low+high)/2； if(R[mid].key==K) return mid； //查找成功返回 if(R[mid].kdy>K) high=mid-1; //继续在R[low..mid-1]中查找 else low=mid+1； /继续在R[mid+1..high]中查找/ } return 0； //当low>high时表示查找区间为空，查找失败 } //BinSeareh 3、二分查找算法 二分查找算法亦很容易给出其递归程序【参见练习】
*4、二分查找的优点和缺点 虽然二分查找的效率高,但是要将表按关键 二字排序。而排序本身是一种很费时的运算。既使 采用高效率的排序方法也要花费O(mgn)的时间。 二分查找只适用顺序存储结构。为保持表的 有序性,在顺序结构里插入和删除都必须移动大 量的结点。因此,二分查找特别适用于那种一经 建立就很少改动、而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表 可采用链表作存储结构,进行顺序查找。链表上 无法实现二分查找。 <心 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 4、二分查找的优点和缺点 虽然二分查找的效率高，但是要将表按关键 字排序。而排序本身是一种很费时的运算。既使 采用高效率的排序方法也要花费O(nlgn)的时间。 二分查找只适用顺序存储结构。为保持表的 有序性，在顺序结构里插入和删除都必须移动大 量的结点。因此，二分查找特别适用于那种一经 建立就很少改动、而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表， 可采用链表作存储结构，进行顺序查找。链表上 无法实现二分查找
5、二分查找的平均查找长度 设内部结点的总数为n=2h-1,则判定树是深 度为h=g(n+1)的满二叉树(深度h不计外部结点)。 树中第k层上的结点个数为2k1,查找它们所需的 比较次数是k。因此在等概率假设下,二分查找 成功时的平均查找长度为: ASL≈lg(n+1)-1 →二分查找在查找失败时所需比较的关键字个数不 超过判定树的深度,在最坏情况下查找成功的比 较次数也不超过判定树的深度。即为:|g(n+1) →二分查找的最坏性能和平均性能相当接近。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 5、二分查找的平均查找长度 设内部结点的总数为n=2h -1，则判定树是深 度为h=lg(n+1)的满二叉树(深度h不计外部结点)。 树中第k层上的结点个数为2 k-1 ，查找它们所需的 比较次数是k。因此在等概率假设下，二分查找 成功时的平均查找长度为： ASLbn≈lg(n+1)-1 二分查找在查找失败时所需比较的关键字个数不 超过判定树的深度，在最坏情况下查找成功的比 较次数也不超过判定树的深度。即为：[lg(n+1)] 二分查找的最坏性能和平均性能相当接近