将排序列表拆分为两个列表

Question

我正在尝试将已排序的整数列表拆分为两个列表。第一个列表将包含以下所有整数n，第二个列表将包含所有以上整数n。请注意，n不一定要在原始列表中。

我可以轻松地做到这一点：

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

但似乎应该可以以更优雅的方式执行此操作，因为知道列表已排序。从itertoolstakewhile来看，这听起来像是解决方案，但随后我会迭代列表两次。dropwhile

从功能上来说，我能做的最好的就是：

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

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

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

我想我正在寻找一种方法来获取返回的列表takewhile和剩余的列表，也许，成对出现。

Answer 1

这里正确的解决方案是modulebisect。用于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)，因此这将通常（在较大的输入上）击败简单地逐个元素地迭代和复制，直到找到分割点。

如果您想最终以代替，请使用bisect.bisect_left( 找到 的最左边的索引n) 而不是bisect.bisect( 相当于) 。bisect.bisect_rightnoverunder