이진 검색
(Binary Search)
: 원소가 오름차순이나 내림차순으로 정렬(sort)된 배열에서 좀더 효율적으로 검색할 수 있는 알고리즘
이진검색의 개념을 이해하기 위해선 UP&DOWN게임을 생각하면 쉽다!
📌 https://www.youtube.com/watch?v=qChFN8jQFQ8 (03:18초 부터 UP&DOWN 게임)
📌 요약)
노홍철이 1~100까지의 숫자 중 하나를 선택하고, 나머지 멤버들이 정해진 기회 안에 맞춰야 하는 게임이다. 멤버들은 정답에 최대한 효율적인 방식으로 다가가고자 중간 숫자인 50을 말한다. 무작정 숫자를 말하기 보다 중간 숫자를 택했기 때문에 앞으로 유추해야할 숫자를 반으로 줄여버릴 수 있었다.
이처럼, 절반을 나누어서 탐색하는 방식을 '이진 검색(Binary Search)'라고 한다.
이진 검색 과정
-
a[mid] < key일 때
a[low] ~ a[mid]는 key보다 작은 것이 분명하므로 검색 대상에서 제외한다. 그리고 검색 범위는 중앙 원소 a[mid]보다 뒤쪽인 a[mid+1] ~ a[high]로 좁혀지게 되어, low값을 mid + 1로 업데이트 한다. -
a[mid] > key일 때
a[mid] ~ a[high]는 key보다 큰 것이 분명하므로 검색 대상에서 제외한다.그리고 검색 범위는 중앙원소 a[mid]보다 앞쪽인 a[low] ~ a[mid-1]로 좁혀지게 되어, high값을 mid - 1로 업데이트 한다.
이진 검색의 종료 조건
- a[mid]와 key가 일치하는 경우
- 검색 범위가 더 이상 없는 경우
코드 구현
from typing import Any, Sequence
def BinarySearch(a:Sequence, key:Any)-> int:
low = 0 # 검색 범위 맨 앞 원소의 인덱스
high = len(a) -1 # 검색 범위 맨 끝 원소의 인덱스
while True:
mid = (low + high) // 2 # 중앙 원소의 인덱스
if a[mid] == key:
return mid # 검색 성공
elif a[mid] < key:
low = mid +1 # 검색 범위를 뒤쪽 절반으로 좁힘
else:
high = mid -1 # 검색 범위를 앞쪽 절반으로 좁힘
if low > high:
break
return -1 # 검색 실페
if __name__ == '__main__':
num = int(input('Number of elements: '))
x = [0] * num # 원소의 수가 num인 배열을 생성
x[0] = int(input('x[0]: '))
for i in range(1, num):
while True:
x[i] = int(input(f'x[{i}]: '))
if x[i] >= x[i-1]: # 바로 직전에 입력한 원솟값보다 큰 값을 입력
break
key = int(input('Input search number: ')) # 검색할 키값 ky를 입력
idx = bin_search(x, key) # ky값과 같은 원소를 x에서 검색
if idx == -1:
print('error')
else:
print(idx)관련 문제
📋 백준 2512: 예산
https://github.com/bmr03016/Coding-Test/blob/main/Baekjoon/%5B2512%5D%20Budget.ipynb
📋 백준 1300: k번째 숫자
https://github.com/bmr03016/Coding-Test/blob/main/Baekjoon/%5B1300%5D%20Kth%20number.ipynb
📋 백준 1654: 랜선 자르기
https://github.com/bmr03016/Coding-Test/blob/main/Baekjoon/%5B1654%5D%20LAN%20cable%20cut.ipynb
📋 백준 3090: 차이를 최소로
https://github.com/bmr03016/Coding-Test/blob/main/Baekjoon/Platinum/%5B3090%5D%20%EC%B0%A8%EC%9D%B4%EB%A5%BC%20%EC%B5%9C%EC%86%8C%EB%A1%9C.ipynb
