👋 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)
