折半查找（二分查找）

文章目录算法思想算法的实现查找效率分析折半查找判定树的构造向下取整向上取整折半查找的查找效率折半查找又称“二分查找”仅适用于有序递增 / 递减 的顺序表。算法思想必须基于顺序存储数组且元素按关键字有序递增/递减。链表无法实现折半查找因为无法随机定位 mid【顺序表拥有随机访问的特性而链表没有】。默认升序设置 low 和 high 指针取中间位置 mid 比较。low查找区间左边界high查找区间右边界m i d ⌊ l o w h i g h 2 ⌋ mid\lfloor \dfrac{lowhigh}{2}\rfloormid⌊2lowhigh​⌋向下取整默认若相等则成功若 key 小于 arr[mid]则 high mid - 1去左半边若 key 大于 arr[mid]则 low mid 1去右半边;循环条件是 low high这是防止漏查最后一个元素;low high查找失败图示如下算法的实现typedefstruct{//查找表的数据结构顺序表ElemType*elem;//动态数组基址intTableLen;//表的长度}SSTable;//折半查找 升序intBinary_Search(SSTable L,ElemType key){intlow0,highL.TableLen-1,mid;while(lowhigh){mid(lowhigh)/2;//取中间位置if(L.elem[mid]key)returnmid;//查找成功则返回所在位置elseif(L.elem[mid]key)highmid-1;//从前半部分继续查找elselowmid1;//从后半部分继续查找}return-1;//查找失败返回-1}// 降序适用于从大到小排列的顺序表intBinary_Search_Desc(SSTable L,ElemType key){intlow0,highL.TableLen-1,mid;while(lowhigh){mid(lowhigh)/2;if(L.elem[mid]key){returnmid;}elseif(L.elem[mid]key){// 【核心区别】中间值 目标值highmid-1;// 目标在左半部分因为左边更大}else{// L.elem[mid] keylowmid1;// 目标在右半部分因为右边更小}}return-1;// 查找失败}查找效率分析查找成功内部结点统计判定树中每一层根为第 1 层的内部结点个数A S L 成功 1 × 第1层结点数 2 × 第2层结点数 . . . h × 第 h 层结点数 n ASL_{成功}\dfrac{1\times\text{第1层结点数}2\times\text{第2层结点数}...h\times\text{第}h\text{层结点数}}{n}ASL成功​n1×第1层结点数2×第2层结点数...h×第h层结点数​查找失败外部结点 / 空指针统计判定树中每个外部结点空指针所在的层数。外部结点的层数等于其父结点的层数 1。公式A S L 失败 ∑ ( 外部结点层数 ) 外部结点总数 ASL_{失败}\dfrac{\sum(\text{外部结点层数})}{\text{外部结点总数}}ASL失败​外部结点总数∑(外部结点层数)​根为第1层。折半查找判定树的构造向下取整向上取整折半查找的查找效率折半查找时间复杂度 O ( l o g 2 n ) O(log_2n)O(log2​n)顺序查找的时间复杂度 O ( n ) O(n)O(n)折半查找的速度 一定 比 顺序查找 更快不一定噢