Python 바이너리 검색
Harshit Jindal
2023년1월30일
노트
이진 검색에 대한 자세한 내용은 이진 검색 알고리즘 문서를 참조하세요.
이진 검색 알고리즘
n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고X요소를 찾으려고합니다.
-
lo를0으로,hi를n - 1로 설정합니다. -
lo<hi동안mid=lo + (hi - lo)/2를 설정합니다.A[mid]==X이면 요소가mid인덱스를 반환하는 것을 발견했습니다.A[mid]<X이면 요소의 왼쪽 절반을 버리고lo를mid+1로 설정합니다.- 그렇지 않으면
A[mid]>X인 경우 요소의 오른쪽 절반을 버리고hi를mid-1로 설정합니다.
-
요소를 찾을 수 없으므로
-1을 반환합니다.
바이너리 검색을위한 Python 프로그램
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 1, 5]
x = 4
n = len(arr)
result = binary_search(arr, x, n)
if result == -1:
print("Element not found")
else:
print("Element is present at index", str(result))
출력:
Element is present at index 2
작가: Harshit Jindal
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