《数据结构（C语言描述）（第2版）》教学课件7-02二分查找

1、2016数据结构Data structure讲授：贺宁 二分查找常州信息职业技术学院0203线性表查找二分查找1、基本思想：设Rlow.high是当前的查找区间。（1）首先确定该区间的中点位置：mid=(low+high)/2;（2）然后将待查找的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：若Rmid.keyK，则由表的有序性可知Rmidn. key均大于K，因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R1mid-1中，故新的查找区间是左子表R1.mid-1；若Rmid.keyK，类似地，则新的查找区

2、间是右子表Rmid+1n。下次在新的查找区间进行查找。二分查找（binary search）：二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：线性表是有序表，即表中结点按关键字有序，不妨设有序表是递增有序的。并且要用顺序存储结构作为表的存储结构。04二分查找 说明从初始的查找区间R1.n开始，每经过一次与当前查找区间的中点位置上结点关键字的比较，若相等则查找成功，否则当前查找区间就缩小一半。重复这一过程直至找到关键字为K的结点，或者当前查找区间为空，即查找失败为止。int BinSearch(SeqList R,KeyType K) /在有序表R1.n中进行二分查找，成功时返回

3、结点位置，失败时返回零int low=1,high=n,mid;/置当前查找区间的初值while(lowK)high=mid-1; /继续在Rlow.mid-1中查找elselow=mid+1;/继续在Rmid+1.high中查找return 0;/当lowhigh时查找区间为空，查找失败 2、具体算法053、二分查找法实例二分查找 已知有序顺序表R（05,13,19,21,37,56,64,75,80,88,92），采用二分查找法查找K=21和K=78。查找过程中，方括号表示当前待查找记录的区间，分别对应下标low和high；下划线表示当前查找记录的关键字，对应下标mid。下标1234567

4、891011K第1次比较051319213756647580889221第2次比较0513192137566475808892第3次比较0513192137566475808892查找K=21的过程如下：查找K=21成功，返回下标mid=4。LH063、二分查找法实例二分查找 已知有序顺序表R（05,13,19,21,37,56,64,75,80,88,92），采用二分查找法查找K=21和K=78。查找过程中，方括号表示当前待查找记录的区间，分别对应下标low和high；下划线表示当前查找记录的关键字，对应下标mid。查找K=78的过程如下：查找K=78不成功，返回0。LH下标1234567891011K第1次比较051319213756647580889278第2次比较0513192137566475808892第3次比较0513192137566475808892区间已空051319213756647580889207二分查找4、算法分析二分查找效率高，但要将表按关键字排序且只适用于顺序存储结构，而不能用于链式存储结构。对经常进行插入和删除操作的表，不