Python의 이진 검색(양등분)

여기에서 우리는 파이썬에서 이등분을 볼 것입니다. bisect는 이진 검색에 사용됩니다. 이진 검색 기술은 정렬된 목록에서 요소를 찾는 데 사용됩니다. 이등분은 하나의 라이브러리 함수입니다.

Python에서 bisect를 사용하는 세 가지 다른 작업을 볼 수 있습니다.

요소의 첫 번째 항목 찾기

bisect.bisect_left(a, x, lo =0, hi =len(a)) 이 함수는 정렬된 목록에서 x의 가장 왼쪽 삽입 지점을 반환하는 데 사용됩니다. 이 경우 마지막 두 매개변수는 선택사항입니다. 이 두 가지는 하위 목록에서 검색하는 데 사용됩니다.

예시

from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i != len(a) and a[i] == x:
      return i
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("First occurrence of", x, "is at position", pos)

출력

First occurrence of 4 is at position 2

x보다 작은 가장 큰 값 찾기

bisect_left 옵션을 사용하면 x(키)보다 작은 더 큰 값을 얻을 수 있습니다.

예시

from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i :
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Larger value, smaller than", x, "is at position", pos)

출력

Larger value, smaller than 8 is at position 4

x가 가장 많이 나타나는 항목 찾기

bisect.bisect_right(a, x, lo =0, hi =len(a)) 이 함수는 정렬된 목록에서 x의 가장 오른쪽 삽입 지점을 반환하는 데 사용됩니다. 이 경우 마지막 두 매개변수는 선택사항입니다. 이 두 가지는 하위 목록에서 검색하는 데 사용됩니다.

예시

from bisect import bisect_right
def BinSearch(a, x):
   i = bisect_right(a, x)
   if i != len(a) + 1 and a[i-1] == x:
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Right most occurrence of", x, "is at position", pos)

출력

Right most occurrence of 36 is at position 9