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

Question

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

我可以轻松地执行此操作：

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

但似乎应该可以以更优雅的方式执行此操作，因为知道列表已排序。 takewhile 和 dropwhile 来自 itertools< /a> 听起来像是解决方案，但随后我会迭代列表两次。

从功能上讲，我能做的最好的事情是：

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

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

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

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

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)，因此这通常（在较大的输入上）会击败简单地逐个元素迭代和复制，直到找到分割点。

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

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]