如何高效查找两个有序数组中差值在固定范围内的元素对？

你当前嵌套循环的时间复杂度是O(n*m)，大数组场景下效率极低。既然两个数组（data1和data2的第3列）已经排序完成，完全可以利用有序性，通过以下两种方法将时间复杂度大幅降低：

方法一：双指针法（时间复杂度O(n+m)） #

利用数组有序的特性，用两个指针分别遍历两个数组，避免无效的元素对比较：

import numpy as np

# 先提取时间列转为numpy数组，比逐行iloc快数倍
times1 = data1.iloc[:, 2].values
times2 = data2.iloc[:, 2].values

timeList = []
i = j = 0
n, m = len(times1), len(times2)
threshold = 100000  # 设定的差值阈值

while i < n and j < m:
    diff = times1[i] - times2[j]
    if abs(diff) <= threshold:
        timeList.append(abs(diff))
        # 数组有序，当前times1[i]仍可能和下一个times2元素匹配，先移动j指针
        j += 1
    elif diff > threshold:
        # times1[i]比times2[j]大太多，移动j也无法缩小差值，直接移动i
        i += 1
    else:
        # times2[j]比times1[i]大太多，移动j指针
        j += 1

方法二：二分查找法（时间复杂度O(n log m)） #

如果其中一个数组规模远大于另一个，用二分查找定位每个元素的匹配区间会更高效：

import numpy as np

times1 = data1.iloc[:, 2].values
times2 = data2.iloc[:, 2].values
timeList = []
threshold = 100000

for t in times1:
    # 找到times2中 >= t-threshold的第一个位置
    left = np.searchsorted(times2, t - threshold, side='left')
    # 找到times2中 <= t+threshold的最后一个位置
    right = np.searchsorted(times2, t + threshold, side='right')
    # 批量计算差值并加入列表
    timeList.extend(np.abs(times2[left:right] - t))

效率对比 #

原嵌套循环会遍历所有元素对，当n、m达到1e4级别时，总操作数是1e8量级；而双指针法仅需2e4次操作，二分查找法仅需1e4*14≈1.4e5次操作，效率提升几个数量级。

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