Python Bisect-이진 검색
이 기사에서는 Python 내장 모듈을 사용하여 바이너리 검색을 수행하는 방법을 살펴 봅니다. bisect모듈은 함수의 근을 찾기위한 이분법 방법을 기반으로합니다. 요소의 인덱스를 찾을 수있는bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right()의 6 가지 함수로 구성됩니다. 또는 목록의 오른쪽 위치에 요소를 삽입합니다. 또한 삽입 후 목록을 정렬하는 데 도움이됩니다. 그러나 제대로 작동하려면 배열이 이미 정렬되어 있는지 확인해야합니다.
bisect.bisect_left()개요
정렬 된 목록 내에서 숫자x의 맨 왼쪽 삽입 지점을 찾는 데 사용됩니다. x가 이미 목록에있는 경우 새x가 목록의 모든x중 가장 왼쪽 위치에 삽입됩니다.
통사론
bisect_left(arr, x, lo=0, hi=len(a))
매개 변수
arr |
입력 목록 |
x |
삽입 지점이있는 요소입니다. |
lo |
목록 하위 집합의 시작 색인을 지정하는 데 도움이됩니다. 기본값은0입니다. |
hi |
목록 하위 집합의 끝 색인을 지정하는 데 도움이됩니다. 기본값은len(arr)입니다. |
반환
배열을 두 개의 절반으로 분할하는 삽입 점을 반환합니다. 첫 번째는 모든 값이x보다 작은 것이고 두 번째는 모든 값이x보다 큰 것입니다.
bisect_left()의 응용 프로그램
첫 번째 요소 찾기
from bisect import bisect_left
def binary_search(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [1, 2, 3, 3, 3]
x = int(3)
res = binary_search(a, x)
if res == -1:
print("Element not Found")
else:
print("First occurrence of", x, "is at index", res)
출력:
First occurrence of 3 is at index 2
x보다 작은 가장 큰 값 찾기
from bisect import bisect_left
def binary_search(a, x):
i = bisect_left(a, x)
if i:
return i - 1
else:
return -1
# Driver code
a = [1, 2, 4, 4, 8]
x = int(7)
res = binary_search(a, x)
if res == -1:
print("There is no value smaller than", x)
else:
print("Largest value smaller than", x, " is at index", res)
출력:
Largest value smaller than 7 is at index 3
bisect.bisect_right()개요
정렬 된 목록 내에서 숫자x의 맨 오른쪽 삽입 지점을 반환하는 데 사용됩니다. x가 이미 목록에있는 경우 새x가 목록의 모든x중 가장 오른쪽에 삽입됩니다.
통사론
bisect_right(arr, x, lo=0, hi=len(a))
매개 변수
arr |
입력 목록 |
x |
삽입 지점이있는 요소입니다. |
lo |
목록 하위 집합의 시작 색인을 지정하는 데 도움이됩니다. 기본값은0입니다. |
hi |
목록 하위 집합의 끝 색인을 지정하는 데 도움이됩니다. 기본값은len(arr)입니다. |
반환
배열을 두 개의 절반으로 분할하는 삽입 점을 반환합니다. 첫 번째는 모든 값이 <=x이고 두 번째는 모든 값이>x입니다.
bisect_right()의 응용 프로그램
요소의 마지막 발생 찾기
from bisect import bisect_right
def binary_search(a, x):
i = bisect_right(a, x)
if i != len(a) + 1 and a[i - 1] == x:
return i - 1
else:
return -1
a = [1, 2, 4, 4]
x = int(4)
res = binary_search(a, x)
if res == -1:
print(x, "is absent")
else:
print("Last occurrence of", x, "is present at", res)
출력:
Last occurrence of 4 is present at 3
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn