Traditional binary search. Performance: O(n log n)

def binary_insert(self, item, priority):
    """Traditional binary search. Performance: O(n log n)"""

    with self.lock:
        self_data = self.data
        rotate = self_data.rotate
        maxlen = self._maxlen
        length = len(self_data)

        index = 0
        min = 0
        max = length - 1

        while max - min > 10:

            mid = (min + max) // 2

            # If index in 1st half of list
            if priority > self_data[mid][1]:
                max = mid - 1

            # If index in 2nd half of list
            else:
                min = mid + 1

        for i in range(min, max + 1):
            if priority > self_data[i][1]:
                index = i
                break
            elif i == max:
                index = max + 1

        shift = length - index

        # Never shift more than half length of depq
        if shift > length // 2:
            shift = length % shift
            rotate(-shift)
            self_data.appendleft((item, priority))
            rotate(shift)
        else:
            rotate(shift)
            self_data.append((item, priority))
            rotate(-shift)

        try:
            self.items[item] += 1
        except TypeError:
            self.items[repr(item)] += 1

        if maxlen is not None and maxlen < len(self_data):
                self._poplast()