[Python] 파이썬에서 이진 탐색(binary search)하기 - bisect

이진 탐색(binary search)

이진 탐색은 정렬된 데이터에서 특정 값을 찾아내는 알고리즘이다.

 

 

bisect 모듈

파이썬에서는 이진 탐색 알고리즘을 기반으로 작동하는 bisect 모듈을 제공한다.

bisect 모듈을 통해 직접 이진 탐색 알고리즘을 구현하지 않고 원하는 원소를 찾을 수 있다.

 

bisect 모듈에서 제공하는 기능

- 원하는 원소 찾기

- 삽입 위치 찾기

- 범위 검색

 

주요 함수

 

bisect.bisect_left(a, x, lo=0, hi=len(a))

: 정렬된 리스트 a에서 값 x보다 크거나 같은 가장 왼쪽 인덱스를 반환한다.

bisect.bisect_right(a, x, lo=0, hi=len(a))

: 정렬된 리스트 a에서 값 x보다 큰 가장 왼쪽 인덱스를 반환한다.

bisect.insort_left(a, x)

: 리스트의 왼쪽부터 탐색해 삽입할 위치를 탐색한다. 함수는 정렬된 리스트에 실행해야 정렬된 결과를 얻을 수 있다. 

bisect.insort_right(a, x)

: 리스트의 오른쪽부터 탐색해 삽입할 위치를 탐색한다. insort_left와 동일하게 정렬된 리스트에 실행해야 정렬된 결과를 얻을 수 있다. 

 

사용 시 주의할 점

- bisect 모듈은 정렬된 리스트에서만 사용할 수 있음. 정렬되지 않은 리스트에서 사용해도 오류가 발생하지는 않는다. 하지만, 정렬되지 않은 리스트에 대해 정렬해주지 않는다.

- bisect 모듈은 원소의 존재 여부를 판단하기 위해 사용할 수는 없다.

- 데이터가 많은 경우에 더 효율적이다.