二分查找Binary search

时间与空间#

n 为元素数；比较操作 $O(1)$，支持 $O(1)$ 随机访问。

时间复杂度

最坏 $O(\log n)$；最好 $O(1)$

辅助空间

迭代实现 $O(1)$

输入已按相同比较规则有序，或谓词满足单调性。链表上的定位移动不是 $O(1)$，总时间可能为 $O(n)$。返回任一匹配、lower_bound 和 upper_bound 的边界规则不同。