Using bisect with tuples in Python

Question

I am trying to understand the use of bisect function in the python's bisect module and how to use it with tuples. I have seen that it takes a list and a value to find the index to place the value. In my case the value is a tuple. This is from leetcode 981. A is a list of tuple and the tuple will contain (int,string) as its data.

class TimeMap(object):
    def __init__(self):
        self.M = collections.defaultdict(list)

    def set(self, key, value, timestamp):
        self.M[key].append((timestamp, value))

    def get(self, key, timestamp):
        A = self.M.get(key, None)
        if A is None: return ""
        i = bisect.bisect(A, (timestamp, chr(127)))
        return A[i-1][1] if i else ""

I understand what they are trying to do for solving the question . I just want to understand why use chr(127). I tried using None but it gives an error. I am guessing that it will always take the first int value in the tuple because the chr(127) will always be unqualified somehow for bisect to accept. But I am not able to find the correct reason for this. also IDLE shows chr(127) as \x7f and found out its a non ascii character.

Alperen · Accepted Answer · 2021-03-08 12:45:40Z

1

Python compares tuples element by element and from left to right. For example:

(1, 2) > (1, 1) is True

(1, 2) > (1, 2) is False

I guess, they use chr(127), to make the second item in the tuple larger than any other character.

(1, chr(127)) > (1, 'z') is True

edited Mar 8, 2021 at 12:45

answered Mar 8, 2021 at 9:17

Alperen

4,8825 gold badges32 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nsingh Over a year ago

you are right. bisect will compare the tuple from left to right and the string value would always be greater than any string in the list of tuples A. as a result bisect will be able to compare correctly. found out in the leetcode discussion forum

nsingh · Accepted Answer · 2021-03-09 02:34:00Z

0

finally found some understanable solution in leetcode discussion forum. all credits go to leetcode users https://leetcode.com/slvher/ and https://leetcode.com/jcodem/

The ascii code range of lower char is [97, 122], thus chr(127) can be used to make sure the located index from bisect.bisect(A, (timestamp, chr(127))) can satisfy the condition: timestamp_prev <= timestamp. In fact, chr(ascii_v) can also be used here where ascii_v's range is [123, 127].

answered Mar 9, 2021 at 2:34

nsingh

811 silver badge6 bronze badges

Collectives™ on Stack Overflow

Using bisect with tuples in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related