파이썬 배열 이분법 알고리즘

이등분 알고리즘은 목록에서 정렬된 상태를 유지하기 위해 데이터를 삽입할 수 있는 위치를 찾는 데 사용됩니다. Python에는 bisect라는 모듈이 있습니다. . 이 모듈을 사용하면 이등분 알고리즘을 사용할 수 있습니다.

이 모듈을 사용하려면 −

import bisect

몇 가지 이등분 관련 작업이 있습니다. 이들은 -

메서드 bisect.bisect(목록, 요소, 시작, 끝)

이 방법은 번호를 배치할 수 있고 목록이 정렬된 상태로 유지되는 정렬된 목록에서 위치를 찾는 데 사용됩니다. 요소가 이미 있는 경우 숫자를 삽입할 수 있는 가장 오른쪽 위치를 반환합니다.

메서드 bisect.bisect_left(목록, 요소, 시작, 끝)

이 메서드는 bisect() 메서드와 동일합니다. 유일한 차이점은 항목이 이미 있는 경우 이 메서드는 데이터를 삽입할 가장 왼쪽 위치를 반환한다는 것입니다.

메서드 bisect.bisect_right(목록, 요소, 시작, 끝)

이 메소드는 bisect() 메소드와 완전히 동일합니다.

메서드 bisect.insort(목록, 요소, 시작, 끝)

이 메소드는 요소를 올바른 위치에 삽입한 후 정렬된 목록을 얻는 데 사용됩니다. 요소가 이미 있는 경우 목록 정렬을 유지하기 위해 가장 오른쪽 위치에 삽입됩니다.

메서드 bisect.insort_left(목록, 요소, 시작, 끝)

이 메소드는 insort() 메소드와 동일합니다. 유일한 차이점은 요소가 이미 있는 경우 목록 정렬을 유지하기 위해 가장 왼쪽 위치에 삽입된다는 것입니다.

메서드 bisect.insort_right(목록, 요소, 시작, 끝)

이 메소드는 insort() 메소드와 완전히 동일합니다.

예시 코드

import bisect
my_list = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]
print('Correct Location to insert 53 is: ' + str(bisect.bisect(my_list, 53, 0, len(my_list))))
print('Correct right Location to insert 69 is: ' + str(bisect.bisect_right(my_list, 69, 0, len(my_list))))
print('Correct left Location to insert 69 is: ' + str(bisect.bisect_left(my_list, 69, 0, len(my_list))))
bisect.insort(my_list, 59, 0, len(my_list))
print(my_list)
bisect.insort_left(my_list, 78, 0, len(my_list))
print(my_list)

출력

Correct Location to insert 53 is: 4
Correct right Location to insert 69 is: 8
Correct left Location to insert 69 is: 5
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120]
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]