二进制搜索：没有获得非常大的值的上限和下限

Question

我正在尝试解决此 cp 问题，UVA - The Playboy Chimp 使用 Python 但出于某种原因，对于非常大的值，例如此输入的答案是错误的：

5
3949  45969  294854  9848573 2147483647
5
10000  6  2147483647  4959 5949583

接受的输出：

3949 45969
X 3949
9848573 X
3949 45969
294854 9848573

我的输出：

X 294854
X 294854
9848573 X
X 294854
45969 9848573

我的代码：

def bs(target, search_space):
    l, r = 0, len(search_space) - 1

    while l <= r:
        m = (l + r) >> 1
        if target == search_space[m]:
            return m - 1, m + 1
        elif target > search_space[m]:
            l = m + 1
        else:
            r = m - 1

    return r, l


n = int(input())
f_heights = list(set([int(a) for a in input().split()]))
q = int(input())
heights = [int(b) for b in input().split()]

for h in heights:
    a, b = bs(h, f_heights)
    print(f_heights[a] if a >= 0 else 'X', f_heights[b] if b < len(f_heights) else 'X')

如有任何帮助，我们将不胜感激！

Answer 1

这是因为您要将第一个输入插入 set，这会更改列表中数字的顺序。如果您使用 Python 3.6 或更新版本 dict维护插入顺序，所以可以用dict.fromkeys维护顺序

f_heights = list(dict.fromkeys(int(a) for a in s.split()))

示例：

f_heights = list(set([int(a) for a in input().split()]))
print(f_heights) # [294854, 3949, 45969, 9848573, 2147483647]

f_heights = list(dict.fromkeys(int(a) for a in input().split()))
print(f_heights) # [3949, 45969, 294854, 9848573, 2147483647]

二进制搜索：没有获得非常大的值的上限和下限

Binary search: Not getting upper & lower bound for very large values

python

algorithm

binary-search