[Python] bisect_left, bisect_right

안녕하세요!

오늘은 python 이 기본 제공하는 이진 탐색 알고리즘을 구현한

bisect 모듈에 대해 알아보겠습니다. 

 

1. 이진 탐색

먼저 이진 탐색이란 탐색 범위를 절반씩 좁혀나가면서 데이터를 탐색하는 알고리즘 입니다.

특히 데이터가 정렬된 상태일 때, 우수한 성능으로 탐색 합니다.

예를 들어 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이라는 배열에서 Target = 3이라면 

1. Middle 값을 기준으로 Target 값이 작은지 큰지 비교합니다.

2. 5 (Middle) > 3 (Target) :  기준 값보다 작으므로 5보다 큰 값들은 비교하지 않고 작은 값 들만 비교합니다.

3. [1, 2, 3, 4] 배열의 중간 값을 기준으로 또 비교를 하는데

4. 여기선 3이 middle이라 치면 target과 동일하므로 탐색을 종료합니다!

 

 

이렇게 계속 middle == target 이 될 때 까지 값을 탐색하는 것을 이진 탐색 이라고 합니다.

모든 배열의 값을 비교하는 것보다 훨씬 효율적인 평균 Θ(log n) 시간이 소요 됩니다!

 

2. bisect

이진 탐색을 사용하여 bisect 라이브러리는 이미 정렬된 정렬된 리스트에서 특정 원소를 찾을 때 효과적 입니다.

자주 사용하는 2가지 함수에 대해 살펴보겠습니다!

1. bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
2. bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

기본적으로 a에 x를 삽입할 위치를 찾는데, bisect_left는 왼쪽에 삽입 bisect_right는 오른쪽에 삽입합니다.

매개변수 lo와 hi는 고려해야 할 리스트의 부분 집합을 지정하는 데 사용할 수 있습니다.

 

a 라는 이미 정렬되어 있는 배열에 x=4 값을 넣을 위치를 찾는다면,

[ bisect_left ]

순서: 0   1   2   3   4   5

값:     1   2   3   4   4   8

                      ^ (삽입할 수 있는 가장 왼쪽인 3~4 사이에 삽입)

배열에 똑같은 값이 있으므로 삽입할 수 있는 가장 왼쪽 인덱스를 찾으면 3 를 반환합니다.

bisect_left는 배열에 값이 같다면 가장 왼쪽에 있는 같은 값의 인덱스 값을 반환합니다. ( =x )

 

[ bisect ,bisect_right ]

순서: 0   1   2   3   4   5

값:     1   2   3   4   4   8

                                 ^ (삽입할 수 있는 가장 오른쪽인 4~8 사이에 삽입)

배열에 똑같은 값이 있으므로 삽입할 수 있는 가장 오른쪽 인덱스를 찾으면 5 를 반환합니다.

bisect, bisect_right는 배열에 값이 같다면 가장 오른쪽에 한칸 뒤의 인덱스 값을 반환합니다. ( >x )

두개가 동일하게 작동됩니다.

 

해당 모듈의 내부 동작코드를 살펴보시면 좀 더 정확하게 이해할 수 있습니다.

python 공식 github 를 참고해주세요 ㅎㅎ

 

---

글 읽어주셔서 감사합니다 😊

공부 하면서 정리 한 내용이라, 혹시 잘못 된 부분이 있으면

얼마든지 댓글로 말씀해주세요!!