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

user_7369790 0
Viewed 61

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!

binary-search algorithm python
1 Answers

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]
user_51680110
Related