빠르고 효율적인 검색 방법, 이진 검색(Binary Search)
이진 검색(Binary Search)은 데이터를 절반으로 나누어가며 검색하는 효율적인 검색 알고리즘입니다.
이번 수업에서는 이진 검색 알고리즘의 개념과 파이썬으로 알고리즘을 구현하는 방법을 알아보겠습니다.
이진 검색이란 무엇인가요?
이진 검색은 정렬된 리스트에서만 사용할 수 있는 검색 알고리즘입니다.
먼저 리스트의 중간에 위치한 값을 확인하고, 이 값이 찾고자 하는 값과 같다면 검색이 완료됩니다.
만약 찾고자 하는 값이 더 작다면 리스트의 왼쪽 절반만을, 더 크다면 오른쪽 절반만을 다시 탐색합니다.
이러한 과정을 반복하여 검색하려는 값을 찾을 때까지 리스트를 절반씩 줄여나갑니다.
이진 검색의 장점
이진 검색의 가장 큰 장점은 검색 범위가 매 단계마다 절반으로 줄어들기 때문에, 검색 속도가 매우 빠르다는 점입니다.
예를 들어 1000개의 데이터가 있을 때, 단순히 첫번째부터 마지막까지 차례대로 검색하는 선형 검색은 최대 1000번의 비교가 필요합니다.
하지만 이진 검색은 최대 10번의 비교만으로도 값을 찾을 수 있습니다.
이진 검색을 파이썬으로 구현하기
이제 파이썬으로 이진 검색을 어떻게 구현할 수 있는지 살펴보겠습니다.
아래 코드는 이진 검색 알고리즘의 기본적인 구현을 보여줍니다.
def binary_search(arr, target):
# 검색 범위의 시작과 끝 인덱스
left, right = 0, len(arr) - 1
# 검색 범위가 좁혀질 때까지 반복
while left <= right:
# 중간 인덱스 계산
mid = (left + right) // 2
# 중간 값 확인
mid_value = arr[mid]
# 중간 값이 목표 값과 일치하는 경우
if mid_value == target:
# 인덱스 반환
return mid
# 중간 값이 목표 값보다 작은 경우
elif mid_value < target:
# 오른쪽 절반을 탐색
left = mid + 1
# 중간 값이 목표 값보다 큰 경우
else:
# 왼쪽 절반을 탐색
right = mid - 1
return -1 # 값을 찾지 못한 경우
# 정렬된 리스트
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
# 이진 검색으로 7 찾기
result = binary_search(numbers, 7)
# 3 출력 (인덱스 3 위치에 값 7이 있음)
print(f"찾는 값의 인덱스: {result}")
코드 설명
-
left와right: 리스트의 검색 범위를 지정하는 변수입니다. 처음에는 리스트의 시작(0)과 끝(len(arr) - 1)을 가리킵니다. -
mid: 검색 범위의 중간 인덱스를 계산합니다.(left + right) // 2는 중간 값을 구하는 코드입니다. -
mid_value: 중간 인덱스에 위치한 값을 의미합니다. 이 값을 목표 값(target)과 비교합니다. -
left = mid + 1: 목표 값이 중간 값보다 크다면, 검색 범위를 오른쪽 절반으로 좁힙니다. -
right = mid - 1: 목표 값이 중간 값보다 작다면, 검색 범위를 왼쪽 절반으로 좁힙니다. -
return -1: 만약 값을 찾지 못한 경우,-1을 반환하여 검색 실패를 알립니다.
다음 내용이 궁금하다면?
코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!