二分查找的时间复杂度为何是log n？我对步数对应复杂度存疑

首先得明确：时间复杂度看的是数据规模n增长时，执行步数的增长趋势，不是某个固定n对应的步数。

• 二分查找的核心逻辑是「每次把待查找范围砍半」：
  比如n=8时，最多找3次（8→4→2→1），3正好是log₂8的结果；n=16时最多找4次，对应log₂16；哪怕n=1024，最多也只需要10次，远不到n的量级。
• 你觉得是O(n)，大概率是和顺序查找搞混了：顺序查找要逐个遍历元素，最坏情况得走n步，所以是O(n)；但二分查找每一步都把问题规模缩小一半，步数的增长速度和n的对数成正比。
• 从数学上推导：假设最多需要k步，每一步后剩余待查规模是原来的1/2，那么经过k步后，剩余规模≤1，也就是n/(2ᵏ) ≤1，解这个不等式得k≥log₂n，所以时间复杂度是O(log n)。

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