求含max-heap的数组中堆的大小x，要求时间复杂度O(logx)

核心思路 #

利用堆的完全二叉树结构和数组随机访问特性，先快速定位接近x的上界，再通过二分查找精准锁定x，整体时间复杂度严格控制在O(logx)，完全适配n极大（如2^100）的场景。

具体步骤 #

1. 快速确定上界

   • 初始化bound = 1，不断将bound翻倍（bound *= 2），直到bound > n或数组第bound-1位（索引从0开始）为无穷大。
   • 例如x=30时，bound会从1→2→4→8→16→32，此时数组第31位是无穷大，停止操作，得到上界32。这一步仅需O(logx)次操作，因为翻倍次数等于x的二进制位数。

2. 二分查找精准定位x

   • 在区间[bound/2, min(bound-1, n)]内进行二分查找：
     • 取中间值mid = (low + high + 1) // 2（向上取整避免死循环）。
     • 检查数组第mid-1位是否为非无穷大：
       • 若是，说明x至少为mid，将low更新为mid。
       • 若否，说明x小于mid，将high更新为mid-1。
   • 最终low（或high）即为所求的x。这一步操作次数同样是O(logx)，因为区间长度不超过x。

替代优化方案（二叉树遍历法） #

从根节点（索引0）出发，利用完全二叉树层级特性遍历：

• 优先检查当前节点的右子节点（索引2*i+2）：
  • 若右子节点非无穷大且未越界，说明堆包含该子节点，直接移动到右子节点继续遍历。
  • 若右子节点是无穷大或越界，则检查左子节点（索引2*i+1），若左子节点有效则移动到左子节点，否则停止。
• 当无法继续向下遍历时，当前路径最末端节点的索引+1即为x。该方法同样是O(logx)时间，步骤更紧凑，适合x较小的场景。

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