关于二分查找算法
💡
原文中文，约10700字，阅读约需26分钟。
📝
内容提要
二分查找算法用于在有序列表中查找元素位置，时间复杂度为O(log n)。通过比较中间值与目标值，逐步缩小查找范围。常见错误包括过早退出、无法退出和剔除目标值。变种upper bound和lower bound用于处理重复元素。
🎯
关键要点
- 二分查找算法用于在有序列表中查找元素位置，时间复杂度为O(log n)。
- 通过比较中间值与目标值，逐步缩小查找范围。
- 常见错误包括过早退出、无法退出和剔除目标值。
- 传统二分查找每次迭代都比较中间值和目标值。
- 如果中间值偏小，剔除中间值及其左边的值；如果偏大，剔除中间值及其右边的值。
- 找到目标值时返回中间值的索引，列表为空时返回-1。
- 常见错误包括过早退出、无法退出、剔除目标值和整型溢出。
- 中途不退出的二分查找减少了一次比较，但需要在仅剩一个元素时判断是否与目标值相等。
- upper bound和lower bound用于处理重复元素，upper bound返回第一个比目标值大的元素。
- lower bound返回第一个等于目标值的元素的地址。
- Knuth的二分查找使用查表的方法来优化中间值的计算。
- 指数查找通过比较指数位置的元素来找到目标值的地址。
➡️
