🔍
二分查找
折半查找超快
📖知识引入
📋必须有序
二分查找的前提是数据已经排好序
✂️每次折半
每次将搜索范围缩小一半，效率极高
⚡O(log n)
时间复杂度为O(log n)，非常高效
🎯三指针
left左边界、right右边界、mid中间点
🔄缩范围
比mid大就left=mid+1，比mid小就right=mid-1
🔍二分查找示例
📝二分查找示例
💻
点击「运行」查看输出
二分查找像猜数字游戏： 在{1,3,5,7,9,11,13,15}中找7
第1次: left=0 right=7 mid=3
arr[3]=7 == 7 找到！如果找5：
第1次: mid=3, arr[3]=7 > 5, right=2
第2次: left=0 right=2 mid=1
arr[1]=3 < 5, left=2
第3次: left=2 right=2 mid=2
arr[2]=5 == 5 找到！┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 3 │ 5 │ 7 │ 9 │11 │13 │15 │ └───┴───┴───┴───┴───┴───┴───┴───┘ L M R
🎯小测验
第1题：二分查找的前提是？
第2题：二分查找时间复杂度？
第3题：arr[mid] < target时应该？
📝本课知识点
- ✓数据必须有序
- ✓每次折半
- ✓O(log n)超快
- ✓left/right/mid三指针
- ✓缩范围找目标
第33课完成！继续探索下一课吧 🚀