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

I’m trying to solve this cp problem, UVA – The Playboy Chimp using Python but for some reason, the answer comes wrong for very large values for example this input:

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

Accepted output:

``````3949 45969
X 3949
9848573 X
3949 45969
294854 9848573
``````

My output:

``````X 294854
X 294854
9848573 X
X 294854
45969 9848573
``````

My code:

``````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')
``````

Any help would be appreciated!

>Solution :

This is because you are inserting the first input to `set`, which changes the order of the numbers in the list. If you are using Python 3.6 or newer
`dict` maintains the insertion order, so you can use `dict.fromkeys` to maintain the order

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

Example:

``````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]
``````