关于二分查找算法

二分查找算法用于在有序列表中查找元素位置，时间复杂度为O(log n)。

通过比较中间值与目标值，逐步缩小查找范围。

常见错误包括过早退出、无法退出和剔除目标值。

传统二分查找每次迭代都比较中间值和目标值。

如果中间值偏小，剔除中间值及其左边的值；如果偏大，剔除中间值及其右边的值。

找到目标值时返回中间值的索引，列表为空时返回-1。

常见错误包括过早退出、无法退出、剔除目标值和整型溢出。

中途不退出的二分查找减少了一次比较，但需要在仅剩一个元素时判断是否与目标值相等。

upper bound和lower bound用于处理重复元素，upper bound返回第一个比目标值大的元素。

lower bound返回第一个等于目标值的元素的地址。

Knuth的二分查找使用查表的方法来优化中间值的计算。

指数查找通过比较指数位置的元素来找到目标值的地址。