有序数组有哪些特点？适合哪些操作？
简化版
有序数组的优势是可以二分查找，查询时间 O(log n)，并且范围遍历很方便；缺点是插入和删除要移动元素，通常是 O(n)。它适合读多写少、数据相对稳定、需要排序遍历和范围查询的场景。
详细版
无序数组查找某个值通常要 O(n)，有序数组可以用二分把查找降到 O(log n)。例如 1024 个元素最多约 10 次比较就能定位。但如果要插入一个新值并保持有序，需要先找位置，再把后面的元素整体右移，移动成本 O(n)。
面试回答要抓住取舍：有序数组把成本前置到写入和维护顺序上，换来更快查询和顺序遍历。它不是万能结构，写多时可能不如平衡树、跳表或哈希表。
完整版教学
一、有序数组维护的是顺序不变式
有序数组要求元素始终按某种规则排列，例如升序。
[2, 5, 8, 13, 21, 34]这个顺序是不变式。所有操作都要维护它：插入新元素要放到正确位置，删除后剩余元素顺序仍然正确。
记忆钩子：有序数组用写入维护顺序，换读取少走弯路。
二、查找可以用二分
有序性最直接的收益是二分查找。每次比较中间元素，就能排除一半范围。
n = 1024
最多比较约 log2(1024) = 10 次无序数组最坏要看 1024 次，有序数组只要约 10 次比较。这就是 O(n) 和 O(log n) 的差距。
简单二分：
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;三、范围查询也很舒服
如果要找 [10, 20] 范围内的所有元素，可以先二分找到第一个大于等于 10 的位置，再向后遍历到大于 20。
[1, 4, 10, 12, 17, 23, 30]
^ start
结果: 10, 12, 17时间可以理解为 O(log n + k)，其中 k 是结果数量。数据库 B+ 树索引的范围查询思想也和有序结构有关。
有序数组适合排行榜快照、只读字典、静态配置表等读多写少场景。
四、插入要移动元素
插入新值 11 到有序数组：
before: [2, 5, 8, 13, 21]
insert 11
after: [2, 5, 8, 11, 13, 21]即使二分 O(log n) 找到了插入位置，后面的 13, 21 仍然要整体右移。最坏插到开头，要移动 n 个元素，所以插入是 O(n)。
这说明查找位置快，不代表插入整体快。
五、删除也要移动元素
删除值 8：
before: [2, 5, 8, 11, 13, 21]
after: [2, 5, 11, 13, 21]删除后要把后面的元素左移填洞。最坏删除第一个元素，要移动 n-1 个元素。
如果删除频繁，有序数组可能不合适。平衡树能用 O(log n) 插入删除并保持有序，跳表也常用于有序集合。
六、和哈希表、平衡树怎么选
| 结构 | 查找 | 插入删除 | 有序遍历 | 范围查询 |
|---|---|---|---|---|
| 有序数组 | O(log n) | O(n) | 很好 | 很好 |
| 哈希表 | 平均 O(1) | 平均 O(1) | 不天然有序 | 不擅长 |
| 平衡树 | O(log n) | O(log n) | 很好 | 很好 |
如果只做等值查询，哈希表通常更快。如果需要范围查询和排序遍历，且写入少，有序数组很简洁。如果写入删除也频繁，平衡树更稳。
七、常见误区与追问
- 误区：有序数组插入是 O(log n)。 二分只找到位置，移动元素仍是 O(n)。
- 误区：有序数组一定比无序数组好。 它牺牲写入维护成本，换查询和范围遍历收益。
- 误区：二分只能找等值。 二分也能找边界，如第一个大于等于、最后一个小于等于。
- 追问：有序数组适合什么场景？ 读多写少、数据稳定、需要范围查询和顺序遍历。
- 追问：写多时用什么替代？ 平衡树、跳表、B+ 树等动态有序结构更合适。
- 追问：为什么范围查询是
O(log n + k)？ 先二分定位边界，再顺序输出 k 个结果。
八、加强记忆
有序数组记成“写时维护顺序，读时享受二分”。它查找 O(log n)，范围查询 O(log n + k)，顺序遍历天然有序；但插入删除要搬移元素，整体 O(n)。读多写少选它很舒服，写多又要有序时考虑平衡树、跳表或数据库索引这类动态有序结构。