规模为4^12的有序列表中前导重复1的高效计数方法探讨

嘿，这个问题问得很到位！针对你这种前导全是1、后续为非1元素的有序列表（比如你提到的规模4^12=16384的[1,1,...1,4]），确实存在比线性遍历更高效的方案，尤其是当列表规模扩大时，性能差异会非常明显。

首选方案：二分查找（内置bisect模块实现） #

因为列表是严格有序的，我们可以利用二分查找快速定位第一个非1元素的索引，这个索引值就是前导1的数量。Python内置的bisect模块是用C实现的，速度比手动写的二分查找还要快，是最优选择。

举个简单的实现例子：

import bisect

def count_leading_ones(arr):
    # 找第一个大于1的元素的插入位置，恰好等于前导1的数量
    return bisect.bisect_left(arr, 2)

为什么用bisect_left(arr, 2)？因为你的列表里只有1和4，2是介于两者之间的数，bisect_left会返回第一个大于2的元素（也就是第一个4）的索引，正好对应前导1的总数。如果列表全是1，这个方法会返回列表长度，也符合预期。

手动实现二分查找（如果不想用内置模块） #

如果你想自己实现二分逻辑，也很简单，核心是缩小查找范围，定位第一个非1元素：

def count_leading_ones(arr):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == 1:
            # 中间元素是1，说明非1元素在右侧，缩小左边界
            left = mid + 1
        else:
            # 中间元素非1，说明目标在左侧，缩小右边界
            right = mid
    return left

为什么这比你当前的方法更优？ #

• 你现在用的线性遍历，最坏情况需要遍历整个列表（比如非1元素在最后一位），时间复杂度是O(n)；
• 二分查找的时间复杂度是O(log n)，对于4^12=16384的列表，最多只需要14次比较就能得到结果，比线性遍历快几个数量级，而且不管非1元素在哪个位置，性能都很稳定。

另外你提到count函数更慢，确实如此——count会遍历整个列表统计1的总数，而你的线性遍历找到第一个非1就中断，但在最坏场景下两者效率差不多，都远不如二分查找。

内容的提问来源于stack exchange，提问作者Tank