为何我的二分查找算法理论为O(log n)时间复杂度却运行缓慢？

你的二分查找算法实际运行缓慢的核心原因是函数参数的传值方式导致了vector的完整复制。

在你的代码中，函数定义是：

int binary_search(int i, vector<int> list)

这里的vector<int> list是按值传递参数，意味着每次调用这个函数时，程序都会创建一个输入vector的完整副本，复制所有元素。这个复制操作的时间复杂度是O(N)，当你的vector规模较大时，这个复制的开销会远远超过二分查找本身O(logN)的计算开销，最终导致整体运行异常缓慢——哪怕你的二分查找循环次数确实符合O(logN)的复杂度，但是前置的复制操作已经把整个函数的时间复杂度拉到了O(N)级别。

修复方案 #

只需要把参数改成引用传递，避免不必要的容器复制：

int binary_search(int i, vector<int>& list)

这样函数会直接操作原vector的数据，不会产生额外的复制开销，二分查找的O(logN)高效性就能正常体现。

另外补充一个小细节：代码中计算中间索引的(max_+min_)/2存在整数溢出风险（当max_和min_都很大时，两者相加可能超出int的范围），可以改用更安全的写法：min_ + (max_ - min_)/2，不过这不是导致当前运行缓慢的直接原因。

内容的提问来源于stack exchange，提问作者Mat Xia