迭代式二分查找的空间复杂度为何始终为O(1)？

首先要明确：我们讨论算法的空间复杂度时，指的是算法运行过程中额外开辟的辅助空间，而非输入数据本身占用的空间——输入空间是问题给定的，不属于算法的空间开销范畴。

迭代式二分查找的核心逻辑，用代码示例来看更清楚：

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

你会发现，不管输入数组arr的规模多大（哪怕对应你说的“高度1000的树”），算法全程只用到left、right、mid这三个固定的变量——它们的数量不会随输入规模n变化，始终是常数个。

你提到的“高度为1的树A和高度为1000的树B”，这是二分查找的逻辑递归树结构，但迭代式实现完全没有递归调用，自然不会为这个逻辑树分配实际的存储空间。只有递归版的二分查找，才会因为递归调用栈的深度等于树的高度，空间复杂度达到O(logn)；而迭代版不需要栈，只用常数个变量，所以额外空间与输入规模无关。

总结来说：迭代式二分查找的额外辅助空间是固定的常数，因此空间复杂度始终为O(1)。

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