数据结构全套配套课件C语言描述第2版李学刚教学课件7-02二分查找.pptx

《数据结构全套配套课件C语言描述第2版李学刚教学课件7-02二分查找.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、在位置mid左边的子表R[1…mid-1]中，故新的查找区间是左子表R[1...mid-1]；②若R[mid].key

3、关键字的比较，若相等则查找成功，否则当前查找区间就缩小一半。重复这一过程直至找到关键字为K的结点，或者当前查找区间为空，即查找失败为止。intBinSearch(SeqListR,KeyTypeK){//在有序表R[1...n]中进行二分查找，成功时返回结点位置，失败时返回零intlow=1,high=n,mid;//置当前查找区间的初值while(low<=high){//当前查找区间R[low...high]非空mid=(low+high)/2;if(R[mid].key==K)returnmi

4、d;//查找成功返回if(R[mid].key>K)high=mid-1;//继续在R[low...mid-1]中查找elselow=mid+1;//继续在R[mid+1...high]中查找}return0;//当low>high时查找区间为空，查找失败}2、具体算法053、二分查找法实例二分查找已知有序顺序表R（05,13,19,21,37,56,64,75,80,88,92），采用二分查找法查找K=21和K=78。查找过程中，方括号[]表示当前待查找记录的区间，分别对应下标low和high；下

5、划线表示当前查找记录的关键字，对应下标mid。下标1234567891011K第1次比较[0513192137566475808892]21第2次比较[0513192137]566475808892第3次比较051319[2137]566475808892查找K=21的过程如下：查找K=21成功，返回下标mid=4。LH063、二分查找法实例二分查找已知有序顺序表R（05,13,19,21,37,56,64,75,80,88,92），采用二分查找法查找K=21和K=78。查找过程中，方括号[]表示当

6、前待查找记录的区间，分别对应下标low和high；下划线表示当前查找记录的关键字，对应下标mid。查找K=78的过程如下：查找K=78不成功，返回0。LH下标1234567891011K第1次比较[0513192137566475808892]78第2次比较051319213756[6475808892]第3次比较051319213756[6475]808892区间已空0513192137566475][80[889207二分查找4、算法分析二分查找效率高，但要将表按关键字排序且只适用于顺序存储结构

7、，而不能用于链式存储结构。对经常进行插入和删除操作的表，不宜采用此方法。①平均查找长度在等概率假设下，二分查找成功时平均查找长度为：最坏情况下查找成功的比较次数为：lg（n+1）。②优缺点THANKS