唐巧的博客
·
CSPJ 教学思考：二分查找
💡
原文中文，约4500字，阅读约需11分钟。
📝
内容提要
二分查找是一种高效的查找算法，通过不断缩小查找范围来快速定位目标值。其基本逻辑是猜测中间值，并根据大小关系调整查找区间。文章还介绍了C++中的lower_bound和upper_bound函数的用法。
🎯
关键要点
- 二分查找是一种高效的查找算法，通过不断缩小查找范围来快速定位目标值。
- 二分查找的基本逻辑是猜测中间值，并根据大小关系调整查找区间。
- 在猜数字游戏中，最佳策略是先猜中间值，然后根据反馈调整猜测范围。
- 二分查找的基本模版包括定义查找范围、计算中间值和更新查找区间。
- 查找范围是闭区间[left, right]，循环条件是left <= right。
- 在查找多个目标值时，需要多次更新结果变量ans。
- 另一种模版使用左闭右开的区间[l, r)，并根据目标值与中间值的关系调整区间。
- C++ STL中的lower_bound函数用于在给定区间内进行二分查找，返回大于或等于目标值的第一个元素位置。
- upper_bound函数返回第一个比目标值大的元素位置，二者的实现逻辑略有不同。
- 二分查找的实现可以通过不同的逻辑来优化查找过程，减少判断次数。
🏷️
标签
➡️
