因此，假设A已经排序，那么可以使用二进制搜索，它已经在（相当笨拙的）bisect模块中的python标准库中提供了：

>>> A = [1.0, 2.9, 3.4, 4.2, 5.5]
>>> B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]
>>> [bisect.bisect_left(A, b) for b in B]
[1, 1, 1, 1, 2, 2, 4]

这需要O(N * logN)时间。
注意，要仔细阅读documentation，当B中的值等于A中的值时，bisect_left和bisect_right的行为，以及不会落在任何地方的项的行为。

你可以在O(n)解决方案中尝试这个方法（假设两个列表都排序了，并且一个数字必须在A中的一个区间内）：

A = [1.0, 2.9, 3.4, 4.2, 5.5, 100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]

grp = 0
i1, i2 = iter(A), iter(B)
a, b = next(i1), next(i2)

out = []
while True:
    try:
        if a < b:
            a = next(i1)
            grp += 1
        else:
            out.append(grp)
            b = next(i2)
    except StopIteration:
        break

print(out)

图纸：

[1, 1, 1, 1, 2, 2, 4]

您可以在O(len(B))中根据以下代码进行回答：

C= [0]*len(B)
i, j = 0, 0

while i < len(B):
    if (B[i] > A[j] and B[i] < A[j+1]):
        C[i] = j
        i += 1
    else:
        j += 1

我认为itertools.groupby加上一个微小的可变“key函数”会非常适合（特别是当需求可能改变，或者您需要在其他地方使用此模式时）：

import itertools

class ThresholdIndexer:
    """Callable that returns the index of the last threshold <= arg.

    Preconditions:
      - thresholds is not empty.
      - thresholds is sorted.
      - For all calls, `thresholds[0] <= call[i].arg <= thresholds[-1]`.
      - For all calls, `call[i - 1].arg <= call[i].arg`.
    """

    def __init__(self, thresholds):
        self.thresholds = thresholds
        self.i = 0

    def __call__(self, arg):
        while not (self.thresholds[self.i] <= arg <= self.thresholds[self.i + 1]):
            self.i += 1
        return self.i 

A = [1.0, 2.9, 3.4, 4.2, 5.5, 100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]

for group_key, group_items in itertools.groupby(B, key=ThresholdIndexer(A)):
    print(f'{group_key}: {", ".join(str(i) for i in group_items)}')

"""Output:
0: 1.1, 1.2, 1.3, 2.5
1: 3.0, 3.1
3: 5.2
"""

这个方法是O（NA + NB）。
你可以通过二进制搜索__call__中的正确索引来消除这些先决条件，而不是假设后面的某个索引“肯定”是正确的，但是复杂度会上升到O（NB × log NA）。

试试这个：

import numpy as np

A = [1.0, 2.9, 3.4, 4.2, 5.5, 100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]
A_arr = np.array(A)
B_arr = np.array(B)
C = [np.searchsorted(A_arr, b) for b in B_arr]
print(C)
>>>
[1, 1, 1, 1, 2, 2, 4]