Python bisect 배열 이진 분할 알고리즘 정리

2022.09.26 - [분류 전체보기] - Binary Tree & Binary Search Tree

Binary Tree & Binary Search Tree

 

이전에 Binary Search Tree가 무엇인지 알아봤었는데요

 

파이썬에서 이러한 배열 이진 분할/삽입이 유용한 함수를 찾아서 탐구해보려합니다 :)

 

√  Bisect 수행 방법

 

From bisect import bisect_left, bisect_right

bisect.bisect_left(list a, 삽입값 x,  lo = 0, hi = len(a))

bisect.bisect_right(list a, 삽입값 x,  lo = 0, hi = len(a))

: 일반적으로 Binary search를 실행하듯이, x가 lo와 h 사이에 왼쪽에 있는지 오른쪽에 있는지를 판별하면서 정렬된 순서에서 a가 x의 어느 부분에 삽입이 되어야 하는지 위치를 찾습니다

 

 

bisect.insort_left(list a, 삽입값 x,  lo = 0, hi = len(a))

: 이 기능은 위의 bisect_left 기능에 항목을 정렬된 순서에 맞게 x 값을 삽입하는 작업을 수행합니다

각 기능을 실행하면 우선적으로 bisect_left이 우선적으로 삽입 위치를 찾기 위해 실행되고 이후에 insert() 메소드를 실행합니다

 

bisect.insort(list a, 삽입값 x,  lo = 0, hi = len(a))

bisect.insort_right(list a, 삽입값 x,  lo = 0, hi = len(a))

: 이 기능은 insort_left() 와 유사하나, 먼저 bisect_right()을 실행하고 삽입한다는 차이점이 있습니다

 

 

 

728x90

---

 

파이썬 공식문서의 예시를 통해서 활용법을 알아보겠습니다

 

숫자 테이블 조회)

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

>> 주어진 점수가 점수구간의 어느 위치에 있는지에 따라 grade 값이 매칭되도록 해서 시험점수에 따른 점수 등급을 나타낸 예시입니다

 

 

이번에는 key값에 대응하는 위치를 반환해서 기존의 어떤 값 위치에 값이 들어가야 하는지를 반환한 예시입니다

 

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])      
>>> keys = [r[1] for r in data] 

>>> data[bisect_left(keys, 0)]
('black', 0)

>>> data[bisect_left(keys, 1)]
('blue', 1)

>>> data[bisect_left(keys, 5)]
('red', 5)

>>> data[bisect_left(keys, 8)]
('yellow', 8)

 

 

---

 

Leetcode에서 괜찮은 Bisect 활용 코드를 발견해서 공유드립니다

Leetcode 981. Time Based Key-Value Store

(https://leetcode.com/problems/time-based-key-value-store/)

 

class TimeMap:

    def __init__(self):
        self.times = collections.defaultdict(list)
        self.values = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect(self.times[key], timestamp)
        return self.values[key][i - 1] if i else ''

 

공식문서의 예시처럼, 3가지 값을 비교해서 위치를 반환해야 할 때 bisect를 많이 쓰는 것 같네요

 

key, value, timestap를 비교해야하기 때문에 get 함수에서 self.times[key] 에서 key 값을 통해 timestamp 가 들어가야 하는 위치를 찾고, 그 위치에 대응되는 value 값을 반환하도록 접근했습니다

 

 

 

---

 

binary search를 매번 코드를 통해 구현하려면 번거로운 점이 많은데

bisect 를 유용하게 사용하면 좋을 것 같습니다!