为什么二分查找的时间复杂度是$O(\log n)$

如何算出来的？背后的数学原理是什么？类似的其他 $\log$ 复杂度的算法，复杂度都是如何推导的？

设问题规模为 n，需要 t 次查找，由二分查找的过程可知，每一次查找问题规模减半，最差情况下，直到问题规模为 1 时才找到或者仍未找到，因此可知：

$$n \times \left(\frac{1}{2}\right) ^t = 1$$

则：

$$2^t = n$$

两边取 $\log$，得

$$t = \log_{2}{n}$$