[파이썬 코딩의 기술] - 72. 정렬된 시퀀스를 검색할 때는 bisect를 사용하라
Q. 리스트에 들어있는 정렬된 데이터를 검색하고 싶을 땐?
bisect
- 파이썬에서 제공하는 표준 라이브러리.
- 이진 검색 알고리즘을 이용해서 시퀀스를 검색하고, 시퀀스에 항목을 삽입할 수 있는 함수 제공
- 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘
- bisect() : 오름차순으로 정렬된 시퀀스에 x값이 들어갈 위치 리턴.
- 기본적으로 시퀀스 전체를 범위로 함.
- bisect_right() : x와 동일한 값이 시퀀스 a에 존재할 때 x와 동일한 값 바로 뒤 위치를 리턴
- bisect_left() : x와 동일한 값이 시퀀스 a에 존재할 때 동일한 값 위치를 리턴. 리스트에 찾는 값의 원소가 존재하지 않는 경우 정렬 순서상 해당 값을 삽입해야 할 자리의 인덱스.
import bisect
sequence = [1,3,4,5]
print(bisect.bisect(sequence,2))
- 2는 [1]위치에 들어가게 됨.
import bisect
sequence = [1, 3, 4, 5]
print(bisect.bisect_right(sequence, 3))
print(bisect.bisect_left(sequence, 3))
-
3이 들어갈 위치 뒷 값은 4 위치 -> [2]
-
동일한 값이 있으므로 3의 위치 -> [1]
-
정렬된 배열 [0,1,2,3,4,5,6,7,8,9] 있을 때, 현재 정렬된 상태를 유지하면서 n=5 이라는 요소를 배열에 추가하자.
-
이분 탐색을 사용하지 않고 구현
-
이분탐색 사용해서 구현
-
bisect 대량 리스트 검색 시 속도 빠름
요약
1. 리스트에 들어 있는 정렬된 데이터를 검색할 때 bisect 내장 모듈의 bisect_left 함수를 사용하자! 시간이 빠르다.
Author And Source
이 문제에 관하여([파이썬 코딩의 기술] - 72. 정렬된 시퀀스를 검색할 때는 bisect를 사용하라), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoonji/파이썬-코딩의-기술-72.-정렬된-시퀀스를-검색할-때는-bisect를-사용하라저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)