Python能有效地找到排序列表中的某个地方吗？

Question

我有一个清单：

x = ['c', 'a', 'e']

我可以排序此列表：

x_sorted = sorted(x)

x_sorted现在是['a', 'c', 'e']

现在假设我有一个新变量y = 'd'

我想找出这个新变量在x_sorted中的位置。在本例中，新变量y包含字符串'd'，因此它将作为['a', 'c', 'd', 'e']放置在列表的索引2中。我希望尽可能有效地找出这个索引号（因为我必须重复这个过程很多次）。你知道吗

下面是我编写的一个函数，它非常简单：

def f(x_sorted, y):
    new_list = x_sorted[:] + [y]
    return sorted(new_list).index(y)

这给了我正确的答案。你知道吗

我想知道是否有更好更有效的方法来做这件事，因为f将被称为100000+次。你知道吗

提前谢谢！你知道吗

Answer 1

这肯定不是您在问题中演示的有效方法，在这种情况下，您每次都对其进行排序，因此如果执行此操作m倍，复杂性将是O(m*n*log(m))，因此首选方法是对其排序一次，然后简单地遍历列表以查找索引，这可以在O(n)中完成，但是最好的方法是使用二进制搜索，现在您的时间复杂度将降到O(log(n))。对于这类问题来说，这是最小的复杂性。你知道吗