给定一个字典和一个浮点数L的列表，如何找到哪个键的值与L中的每个值最接近？

Question

Input1.输入

d = {1: 0.2, 2: 0.4, 3: 0.5, 4: 0.5, 5: 0.5, 6: 0.7, 7: 0.7, 8: 0.8, 9: 0.95, 10:1}
L = [0.48, 0.72]

预期的结果1: [3, 6] [3, 6]

输入2:

d = {1: 0.9, 2: 0.88, 3: 0.88, 4: 0.76, 5: 0.76, 6: 0.7, 7: 0.5, 8: 0.44, 9: 0.2, 10:0}
L = [0.48, 0.77]

预期结果2： [7, 4]

你可以假设d中的值是排序的(总是随着键的变大而增加或减少)如果有值是相等的，就返回最小的键。

我能够在O(n)内完成，有没有更好的方法用二进制搜索来完成？

Answer 1

一个可能的解决方案--没有经过彻底的测试--但它并不比O(n)好。

def find_closest(source: dict, targets: list) -> list:
    result = {}
    for idx, target in enumerate(targets):
        last = None
        for key, val in source.items():
            if not last or abs(target - val) < last:
                last = abs(target - val)
                result[idx] = key
            elif abs(target - val) > last:
                break
    result = list(result.values())
    return result


if __name__ == '__main__':
    d1 = {1: 0.2, 2: 0.4, 3: 0.5, 4: 0.5, 5: 0.5, 6: 0.7, 7: 0.7, 8: 0.8, 9: 0.95, 10: 1}
    L1 = [0.48, 0.72]

    d2 = {1: 0.9, 2: 0.88, 3: 0.88, 4: 0.76, 5: 0.76, 6: 0.7, 7: 0.5, 8: 0.44, 9: 0.2, 10: 0}
    L2 = [0.48, 0.77]

    d3 = {1: 0.1, 2: 0.2, 3: 0.3, 4: 0.4, 5: 0.5, 6: 0.6, 7: 0.7, 8: 0.8, 9: 0.9, 10: 1.0}
    L3 = [0.48, 0.77]

    d4 = {1: 0.9, 2: 0.8, 3: 0.7, 4: 0.6, 5: 0.5, 6: 0.4, 7: 0.3, 8: 0.2, 9: 0.1, 10: 0.0}
    L4 = [0.48, 0.77]

    print(find_closest(d1, L1))
    print(find_closest(d2, L2))
    print(find_closest(d3, L3))
    print(find_closest(d4, L4))

[3, 6]
[7, 4]
[5, 8]
[5, 2]