파이썬 문법
[알고리즘] 이진 탐색(Binary Search)
토리쟁이
2024. 4. 1. 20:47
이번 포스팅에서는 파이썬 코테에 자주 등장하는 유형 중 하나인, 이진 탐색 알고리즘에 대해 공부해보려고 한다.
이진 탐색(Binary Search)
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 알고리즘
- 반드시, 정렬된 리스트에서 사용해야 함
- 찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교해서 크기가 작으면 중간점을 왼쪽으로 옮기고, 크기가 크면 중간점을 오른쪽으로 옮기는 과정을 반복
- 시간 복잡도는 O(logN)
이진 탐색은 재귀함수 또는 반복문으로 구현할 수 있으며, 아래의 코드는 반복문으로 구현한 코드이다.
def binary_search(arr, target):
start = 0
end = len(arr)-1
while start<=end:
mid = (start+end)//2 # 탐색 범위의 중간 인덱스
if arr[mid] == target:
return mid
elif arr[mid] > target: # 찾고자하는 데이터가 중간에 위치한 데이터보다 작은 경우
end = mid -1 # 탐색 범위를 왼쪽 절반으로 설정
else: # 찾고자하는 데이터가 중간에 위치한 데이터보다 큰 경우
start = mid + 1 # 탐색 범위를 오른쪽 절반으로 설정
return None
target = int(input())
arr = list(map(int, input().split()))
arr.sort() # 반드시 정렬 후 이진 탐색 진행할 것
result = binary_search(arr, target)
Python에서는 bisect라는 이진 탐색 라이브러리를 지원한다.
bisect
- from bisect import bisect_left, bisect_right
- bisect_left(a, x): 정렬된 순서를 유지하면서 리스트a에 x 데이터를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
- bisect_right(a, x): 정렬된 순서를 유지하면서 리스트a에 x 데이터를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
- 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수를 구할 때 용이
아래는, bisect 모듈을 이용하여 특정 범위에 속하는 원소의 개수를 구하는 코드이다.
from bisect import bisect_left, bisect_right
num_list = [9,1,5,3,4,2,8,8,7]
num_list.sort() # [1, 2, 3, 4, 5, 7, 8, 8, 9]
# 8의 개수 찾기
cnt = bisect_right(num_list, 8) - bisect_left(num_list, 8) # 8-6 = 2
# 특정 범위에 속한 데이터의 개수 구하기 ex) 1~4
print(bisect_right(num_list, 4) - bisect_left(num_list, 1)) # 4-0 = 0
참고