👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻
感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏
算法思想
折半查找,又称 二分查找,仅适用于 有序 的 顺序表
使用两个指针,一个 low
在开头一个 high
在结尾
查找目标只可能在
[
l
o
w
,
h
i
g
h
]
[low,high]
[low,high] 区间内
最终 low
和 high
指针重叠,都指向某个位置 i
那么最终的 mid = (low + high) / 2 = i
这个时候,如果指向的元素就是要查找的元素,那么查找成功
但是也会出现查找失败的情况,也就是最终指向的时候,low < high
或者 元素不存在
实现
int Binart_Search(SSTable L, ElemType key){
int low = 0, high = L.TableLen-1, mid;
while(low <= high){
mid = (low + high) / 2; // 取中间位置
if(L.elem[mid] == key)
return mid; // 查找成功则返回所在位置
else if(L.elem[key] > key)
high = mid - 1; // 从前半部分继续查找
else
low = mid + 1; // 从后半部分继续查找
}
return -1 // 查找失败,返回 -1
}
折半查找判定树的构造
- 如果当前
low
和high
之间有 奇数个 元素,则mid
分隔后,*左右两部分元素个数相等 - 如果当前
low
和high
之间有 偶数个 元素,则mid
分隔后,左半部分比右半部分少一个元素
折半查找判定树一定是平衡二叉树
折半查找的判定树中,只有最下面一层是不满的
因此,元素个数为 n 时树高
h
=
[
l
o
g
2
(
n
+
1
)
]
h=[log_2(n+1)]
h=[log2(n+1)] ,直接反映了时间复杂度
判定树结点关键字:
左
<
中
<
右
左<中<右
左<中<右 ,满足二叉排序树的定义
失败节点 :n+1个(等于成功节点的空链域数量)
树高 h = [ l o g 2 ( n + 1 ) ] h=[log_2(n+1)] h=[log2(n+1)] —— 查找成功的 A S L ≤ h ASL\leq h ASL≤h ,查找失败的 A S L ≥ h ASL\geq h ASL≥h ,折半查找的时间复杂度 = O ( l o g 2 n ) =O(log_2n) =O(log2n)