2022-07-05 @이영훈
이진탐색 알고리즘을 기록으로 남깁니다.
나동빈님의 이진 탐색 유튜브 영상을 참고하였습니다.
이진 탐색 (Binary Search)
이진 탐색 알고리즘은 오름차순 또는 내림차순으로 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.
이진 탐색 동작 과정
[문제 조건] 정렬된 10개의 데이터 중에서 값이 찾는값(target) 4인 원소를 찾습니다.
[Step1] 시작점(start)을 0번, 끝점(end)을 9번, 중간점(middle)을 (0 + 9) // 2 = 4 로 초기화 합니다.
[Step2] target이 중간점의 값(arr[middle])보다 작기 때문에 끝점을 중간점보다 하나 작게 설정합니다
•
end = middle - 1
[Step3] 이번에는 중간점 값(arr[middle])이 target보다 작기 때문에 시작점을 중간점보다 하나 더 크게 설정합니다.
•
start = middle + 1
이진 탐색의 시간 복잡도
•
단계마다 탐색 범위를 절반으로 줄이기 때문에 시간 복잡도는 O(logN)입니다.
•
정렬된 데이터가 많을 때 (1억개 이상) 순차 탐색보다는 이진 탐색으로 접근하는 것이 좋습니다.
파이썬 코드
반복문으로 구현
def binary_search(arr: List[int], target: int):
start = 0
end = len(arr) - 1
while start <= end:
middle = (start + end) // 2
if arr[middle] == target:
return middle
elif arr[middle] > target:
end = middle - 1
else: # arr[middle] < target:
start = middle + 1
return -1
Python
복사
재귀적으로 구현
def binary_search(arr: List[int], target: int, start: int, end: int):
if start > end:
return -1
middle = (start + end) // 2
if arr[middle] == target:
return middle
elif arr[middle] < target:
return binary_search(arr, target, middle + 1, end)
else: # arr[middle] > target:
return binary_search(arr, target, start, middle - 1)
Python
복사