将已排序的列表分成两个列表。

Question

我想把一个排序好的整数列表分成两个列表。第一个列表包含所有小于n的整数，第二个列表包含所有大于n的整数。请注意，n不一定在原始列表中。

我可以很容易地使用以下方法做到这一点：

under = []
over  = []
for x in sorted_list:
    if x < n:
        under.append(x)
    else
        over.append(x)

但是，既然已知列表已排序，似乎应该有更加精妙的方法来完成这个任务。itertools 中的 takewhile 和 dropwhile 看起来像是解决方案，但那样我将会对列表进行两次迭代。

就功能而言，我所能做到的最好的办法是：

i = 0
while sorted_list[i] < n:
    i += 1

under = sorted_list[:i]
over = sorted_list[i:]

但我甚至不确定它是否比两次迭代列表更好，而且它绝对不够优雅。

我想我正在寻找一种方法来以一对的形式返回takewhile 返回的列表和剩余的列表。

- CarlosHSF

---

最好使用二分查找来查找索引。 - Rishabh Deep Singh

Answer 1

这里的正确解决方案是 bisect 模块。使用 bisect.bisect 找到在 n 右侧的索引（或者如果该索引不存在，则找到可插入位置的索引），然后在该点处进行切片：

 import bisect # At top of file

 split_idx = bisect.bisect(sorted_list, n)
 under = sorted_list[:split_idx]
 over = sorted_list[split_idx:]

虽然任何解决方案都将是 O(n)（毕竟您必须复制元素），但比较通常比简单的指针复制（和相关的引用计数更新）更昂贵，并且 bisect 将排序后的 list 上的比较工作减少到 O(log n)，因此这通常（在较大的输入上）会击败仅迭代并逐个复制元素直到找到分割点。

如果您希望 n 最终位于 over 而不是 under，请使用bisect.bisect_left（查找 n 的最左索引）而不是 bisect.bisect（相当于 bisect.bisect_right）。

- ShadowRanger

---

关于速度，我会说这不是真正的“对象比较与指针复制”，而是“对象比较与引用计数增量”。也许可以在O(s)时间内完成，其中s是第二部分中元素的数量。使用over = sorted_list[split_idx：]、del sorted_list[split_idx：]和under = sorted_list（不确定del的实际复杂度）。 - Kelly Bundy

@KellyBundy：当然，引用计数增量操作在分段内存上操作，所以它们可能比指针复制要昂贵一些。无论如何，你都需要支付它们的代价（指针复制也是如此），但两者都比比较的成本微不足道。如果您不需要保留原始的“sorted_list”，那么您可以将其用作“under”，并将复制到“over”中的部分删除（从“list”的末尾进行“del”实现得尽可能高效；最坏的情况是，它重新分配空间并必须“O(n)”复制幸存的指针，而不触及refcnts）。 - ShadowRanger

指针复制也一样吗？我不这么认为。它们在内存中是顺序处理的。请参见此处。复制列表比重复/反转/前置/取消前置（类似于纯指针复制）慢了约30倍。 - Kelly Bundy

@KellyBundy：不好意思，我的意思不是你的优化没有通过避免指针复制来节省任何东西（我的最后一句话承认你的优化重用了“sorted_list”，确实避免了对一半的“list”进行refcnt操作，而我在评论开头就说过refcnt操作比原始指针复制更昂贵）。我的意思是，在我的代码和OP提出的解决方案中（所有这些解决方案都保留了“sorted_list”完整），你必须支付指针复制和refcnt操作成本（它们比比较便宜得多）。 - ShadowRanger

哦，我不再谈论我的优化想法了。我只是在提到你的回答中谈到指针复制而没有提到引用计数增加，因为我认为后者更重要。至于它们中的任何一个与对象比较：我需要检查一下。你可以看到我的第一个实验包括 a.sort()，其中包括比较，并且与 a[:] 一样快。尽管这是由于 sort 中的优化，而不是使用常规对象比较。 - Kelly Bundy

Answer 2

我会使用以下方法，在其中找到索引并使用切片创建under和over:

sorted_list = [1,2,4,5,6,7,8]
n=6

idx = sorted_list.index(n)
under = sorted_list[:idx]
over = sorted_list[idx:]

print(under)
print(over)

输出（与您的代码相同）：

[1, 2, 4, 5]
[6, 7, 8]

编辑：由于我误解了问题，这里提供了一种适应性更强的解决方案来查找最近的索引：

import numpy as np

sorted_list = [1,2,4,5,6,7,8]
n=3

idx = np.searchsorted(sorted_list, n)
under = sorted_list[:idx]
over = sorted_list[idx:]

print(under)
print(over)

输出：

[1, 2]
[4, 5, 6, 7, 8]

- JANO

---

谢谢，但我应该更详细地描述问题。实际上，我不知道列表中的整数是什么，因此可能没有要查找索引的“n”。 - CarlosHSF

如果您不知道在哪里拆分，该如何确定拆分点？或者如果 n 是 None，是否应该有默认的拆分点？ - JANO

考虑 sorted_list = [1,3] 和 n = 2 的情况。 在这种情况下，under = [1]，over = [3]。然而，2 不在 sorted_list 中。 - CarlosHSF

好的，我明白了。我添加了另一种解决方案，它可以为缺失值提供正确的索引。 - JANO