如何在Binary Search算法中查找多个匹配值？原算法仅返回首个结果

当然可以！完全能通过二分查找的变种来找到所有匹配值，我给你详细讲讲怎么实现～

首先要确认你的数据是按目标查找键有序排列的——从你给出的输入来看，相同编号（比如00001）的记录都集中在一起，之后才是00002，完美满足二分查找的要求。

这种方法的思路是先用两次二分查找，分别定位到目标值的第一个出现位置（左边界）和最后一个出现位置（右边界），然后两个边界之间的所有元素就是你要的全部匹配值。相比找到一个匹配后再线性遍历，这种方法的时间复杂度还是O(log n)（两次二分），再加上提取匹配元素的O(k)（k是匹配数量），在大数据量下效率高很多。

代码示例（Python） #

先把你的输入整理成结构化的列表（方便操作）：

# 模拟你的输入数据，后续00002的记录可以继续补充
data = [
    ("00001", 1521065760, "38 42' 50\"", "-9 8' 22\""),
    ("00001", 1521066360, "38 42' 4\"", "-9 45' 24\""),
    ("00001", 1521066960, "38 41' 18\"", "-9 22' 26\""),
    ("00001", 1521067560, "38 40' 32\"", "-8 59' 28\""),
    ("00001", 1521068160, "38 39' 46\"", "-8 36' 30\""),
    ("00001", 1521068760, "38 39' 2\"", "-8 13' 32\""),
    ("00001", 1521069360, "38 34' 0\"", "-7 54' 0\""),
    ("00001", 1521069960, "38 34' 0\"", "-7 54' 0\""),
    ("00002", 1521070560, "...", "...")  # 后续数据
]

1. 实现左边界查找函数 #

这个函数会找到目标键第一次出现的索引：

def find_left_bound(data, target_key):
    left, right = 0, len(data) - 1
    left_bound = -1  # 默认没找到
    while left <= right:
        mid = (left + right) // 2
        if data[mid][0] == target_key:
            left_bound = mid
            right = mid - 1  # 找到匹配后继续向左，找更早的出现位置
        elif data[mid][0] < target_key:
            left = mid + 1
        else:
            right = mid - 1
    return left_bound

2. 实现右边界查找函数 #

这个函数会找到目标键最后一次出现的索引：

def find_right_bound(data, target_key):
    left, right = 0, len(data) - 1
    right_bound = -1  # 默认没找到
    while left <= right:
        mid = (left + right) // 2
        if data[mid][0] == target_key:
            right_bound = mid
            left = mid + 1  # 找到匹配后继续向右，找更晚的出现位置
        elif data[mid][0] < target_key:
            left = mid + 1
        else:
            right = mid - 1
    return right_bound

3. 提取所有匹配值 #

target = "00001"
left_idx = find_left_bound(data, target)
right_idx = find_right_bound(data, target)

if left_idx != -1 and right_idx != -1:
    all_matches = data[left_idx:right_idx + 1]
    print(f"找到 {len(all_matches)} 个匹配结果：")
    for item in all_matches:
        print(item)
else:
    print("没有找到匹配的记录")

如果你的数据量不大，也可以用更简单的方法：先用普通二分找到第一个匹配的位置，然后向左、向右分别遍历，收集所有相同的元素。这种方法代码更简洁，但如果匹配元素很多，效率会接近O(n)。

示例代码：

def find_all_matches(data, target_key):
    # 先找第一个匹配的位置
    left, right = 0, len(data)-1
    first_pos = -1
    while left <= right:
        mid = (left + right) // 2
        if data[mid][0] == target_key:
            first_pos = mid
            right = mid -1
        elif data[mid][0] < target_key:
            left = mid +1
        else:
            right = mid -1
    
    if first_pos == -1:
        return []
    
    # 向左遍历找所有匹配
    start = first_pos
    while start > 0 and data[start-1][0] == target_key:
        start -=1
    
    # 向右遍历找所有匹配
    end = first_pos
    while end < len(data)-1 and data[end+1][0] == target_key:
        end +=1
    
    return data[start:end+1]

# 使用示例
matches = find_all_matches(data, "00001")
print(f"找到 {len(matches)} 个匹配")
for match in matches:
    print(match)

• 如果你的查找键不是第一个字段（比如是时间戳），只需要把代码中data[mid][0]的索引改成对应的位置（比如时间戳是第二个字段就用data[mid][1]）。
• 一定要保证数据是按查找键有序排列的，否则二分查找根本无法正确工作。
• 如果没有找到匹配值，两个边界函数都会返回-1，这时候要做判断避免索引越界错误。

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