求大型无重复有序整数数组中找出2的幂元素的高效解法

原解法的问题 #

你原来的遍历数组+用log(n)/log(2)判断的思路，空间复杂度确实是O(1)，但面对极大规模数组时，O(n)的遍历效率太低了。而且对数计算还有个坑：浮点数精度误差可能导致误判——比如大的2的幂，计算后可能因为精度丢失得到非整数结果，把正确的元素漏掉。

更高效的优化方案 #

既然数组是有序无重复的，咱们换个反向思路：生成所有可能的2的幂，然后对每个幂用二分查找在数组里确认是否存在，具体步骤如下：

• 先拿到数组的最大值max_val，以此为上限，从2^0=1开始生成所有2的幂，直到生成的数超过max_val为止
• 对每个生成的2的幂，在有序数组里做二分查找，找到就加入结果

为什么这方法更高效？ #

时间复杂度是O(log(max_val) * logN)：log(max_val)是要生成的2的幂的数量——哪怕数组最大值是2^60，也只需要生成60个2的幂；logN是单次二分查找的时间。对比O(n)的遍历，面对极大数组时效率提升不是一点半点。空间复杂度依然是O(1)（除了存结果的空间）。

更可靠的2的幂判断方法（替代对数计算） #

如果还是想用遍历的思路，也可以把对数判断换成位运算：正整数n是2的幂的充要条件是n & (n-1) == 0且n != 0。这个方法完全没有浮点数精度问题，比对数判断靠谱得多。

伪代码示例 #

def find_power_of_two(arr):
    result = []
    if not arr:
        return result
    max_val = arr[-1]
    current = 1
    while current <= max_val:
        # 二分查找current是否在数组中
        left, right = 0, len(arr) - 1
        found = False
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == current:
                found = True
                break
            elif arr[mid] < current:
                left = mid + 1
            else:
                right = mid - 1
        if found:
            result.append(current)
        # 生成下一个2的幂，用左移比乘法更快
        current <<= 1
    return result

注意事项 #

如果数组最大值超大（超过所用语言的整数范围），生成2的幂时要加溢出判断，防止无限循环。

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