如何找到降序一维数组中累加和≥目标值的索引？

假设有一个按降序排列的一维数组，示例如下：
arr = np.array([10, 10, 8, 5, 4, 4, 3, 2, 2, 2])

需求是找到最小的索引，使得从数组起始位置到该索引的累加和大于或等于指定目标值。例如目标值为40时：

index=0（范围0）=> sum=10（10）
index=1（范围0,1）=> sum=20（10+10）
index=2（范围0,1,2）=> sum=28（10+10+8）
index=3（范围0,1,2,3）=> sum=33（10+10+8+5）
index=4（范围0,1,2,3,4）=> sum=37（10+10+8+5+4）
index=5（范围0,1,2,3,4,5）=> sum=41（10+10+8+5+4+4）

最终应返回索引5，因为此时累加和首次≥目标值40。以下是适配大数和大型数组的高效Python实现方案：

高效实现思路 #

数组是降序排列，但前缀累加和必然是非递减的（假设数组元素均为非负数），因此可以结合前缀和计算+二分查找的组合，将时间复杂度从逐一遍历的O(n)优化为O(n)（计算前缀和）+ O(logn)（二分查找），大幅提升大型数组的处理效率。

方案1：基于Numpy实现（适合超大型数值数组） #

Numpy的向量化操作计算前缀和效率极高，配合searchsorted方法实现二分查找：

import numpy as np

def find_min_index(arr, target):
    # 计算前缀和数组，prefix_sum[i]对应arr[0..i]的累加和
    prefix_sum = np.cumsum(arr)
    # 查找第一个≥target的元素索引
    index = np.searchsorted(prefix_sum, target, side='left')
    # 处理所有元素累加和仍小于目标值的边界情况
    return index if prefix_sum[-1] >= target else -1

# 测试示例
arr = np.array([10, 10, 8, 5, 4, 4, 3, 2, 2, 2])
target = 40
print(find_min_index(arr, target))  # 输出5

方案2：纯Python实现（无需第三方库） #

借助bisect模块，配合手动计算前缀和，适合非Numpy场景：

import bisect

def find_min_index(arr, target):
    prefix_sum = []
    current_sum = 0
    for num in arr:
        current_sum += num
        prefix_sum.append(current_sum)
        # 提前终止：当前和已达标时无需继续计算后续前缀和
        if current_sum >= target:
            break
    # 二分查找第一个≥target的位置
    index = bisect.bisect_left(prefix_sum, target)
    # 处理边界情况
    return index if (prefix_sum and prefix_sum[-1] >= target) else -1

# 测试示例
arr = [10, 10, 8, 5, 4, 4, 3, 2, 2, 2]
target = 40
print(find_min_index(arr, target))  # 输出5

效率说明 #

• 两种方法的时间复杂度均为O(n)+O(logn)，对于百万级以上的大型数组，比逐一遍历的O(n)方法效率更高；纯Python版本在目标值对应的位置靠前时，还能通过提前终止进一步节省计算资源。
• Numpy版本利用底层C实现的向量化操作，计算前缀和的速度远快于纯Python循环，是超大型数值数组的最优选择。

内容的提问来源于stack exchange，提问作者Mert Can Basut