如何基于1D二分查找算法实现Python二维数组按出生年查询全量匹配员工ID

• 找到单个匹配项后直接return ids结束函数，没有收集排序后连续排列的其余同年份员工ID，自然只能返回1个结果
• ids定义为全局变量，每次调用函数不会自动清空，多次调用会出现结果累加的错误
• 未匹配到目标年份时返回False，和要求返回列表的输出类型不统一
• 最初的扁平化思路逻辑错误，会将员工ID和出生年份混在同一维数组中查询，无法对应ID和年份的绑定关系

按出生年份对数组做升序排序后，相同年份的记录必然是连续排列的，基于原有的二分逻辑做两次二分查询即可：第一次找到第一个等于目标年份的记录下标（左边界），第二次找到最后一个等于目标年份的记录下标（右边界），最后提取两个边界之间的所有员工ID即可。

def get_IDs_with_birthyear(year, employee_with_birthyear_list):
    # 按出生年份升序排序
    sorted_data = sorted(employee_with_birthyear_list, key=lambda x: x[1])
    n = len(sorted_data)
    if n == 0:
        return []
    
    # 第一次二分：找左边界（第一个等于目标年份的下标）
    left, right = -1, n
    while left + 1 < right:
        mid = (left + right) // 2
        if sorted_data[mid][1] >= year:
            right = mid
        else:
            left = mid
    # 无匹配直接返回空列表
    if right >= n or sorted_data[right][1] != year:
        return []
    left_bound = right
    
    # 第二次二分：找右边界（最后一个等于目标年份的下标）
    left, right = -1, n
    while left + 1 < right:
        mid = (left + right) // 2
        if sorted_data[mid][1] <= year:
            left = mid
        else:
            right = mid
    right_bound = left
    
    # 提取区间内所有ID
    return [item[0] for item in sorted_data[left_bound:right_bound+1]]

测试示例 #

list2 = [[2, 1986],
 [4, 1950],
 [6, 1994],
 [9, 2004],
 [12, 1988],
 [13, 1964],
 [16, 1987],
 [18, 1989],
 [19, 1951],
 [20, 1991]]

print(get_IDs_with_birthyear(1986, list2)) # 输出 [2]

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