二分查找能以 O(log n) 找到有序数组的插入位置。为什么完整插入仍可能是 O(n)？

二分查找能以 O(log n) 找到有序数组的插入位置。为什么完整插入仍可能是 O(n)？

1. 后续元素可能都要移动，才能腾出一个数组槽位。
2. 二分查找定位后还会比较数组中的每个元素。
3. 稳定排序要求每次插入都重建哈希表。