이진탐색 이란?
- 이름에서 알 수 있듯 이진탐색은 탐색 범위를 반으로 쪼개면서 탐색하는 방법이다.
- 이진탐색이라는 정렬되어 있는 리스트 혹은 트리에서 사용 가능한 알고리즘이다.
이진탐색의 예
업 다운 게임
업 다운 게임은 흔히 술자리에서 많이하는 게임으로 소주병 뚜껑에는 1 ~ 50까지의 숫자 중 한가지의 수가 적혀 있다.
상대방이 숫자를 부르면 UP 또는 DOWN으로 알려줘 제한된 회수 안에 숫자를 맞춰야 하는 게임이다.
그렇다면 어떻게 하면 이길 확률이 높아질까?
물론 운좋게 50분의 1 확률로 찍는 것이 가장 좋은 방법이다. 하지만 최악의 경우를 고려해 보면 이는 좋은 방법이 아니며 최적의 방법은 존재한다.
이진탐색
최적의 방법은 범위의 중간값을 부르는 경우이다.
- 예를들어 정답이 1 이고 중간값중 소수점은 반올림 한다고 가정해보자
- 첫 범위는 최솟값이 1 최대값이 50 이므로 중간 값인 25.5에서 반올림한 26을 선택한다.
- 두 번째 범위는 1~ 25이 되며 같은 방식으로 중간값 13를 선택한다.
- 이를 반복하면 26 → 13 → 7 → 4 → 2 → 1 의 결과에 도달한다.
이렇게 항상 범위의 중간값을 부르게 되면, 최악의 경우에도 범위가 반으로 좁혀지며 $log_{2}{(50)}$ = 5.64 즉 6번 안에 항상 해를 구할 수 있다.
이진탐색의 시간 복잡도
위의 경우에서 보듯 log_2(N)의 시간이 필요로하며 Big-O 표기법으로는 O(log(N)) 이 보장된다. 이는 순차탐색의 시간복잡도인 O(N)과 대비된다.
코팅테스트에서의 이진탐색
이진탐색의 개념은 단순하다. 하지만 이를 코테에서 구현하는 일은 아주 간단하지 만은 않다. 또한 이진탐색 단독으로 문제가 출제되는 경우도 있지만 다른 알고리즘과 함께 사용되는 경우도 빈번하다. 그렇기 때문에 코드의 구조를 암기하는 것이 도움이 될 것 같다.
이진탐색의 구현
- 재귀를 이용한 구현
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid + 1, end)
# n(원소의 개수)와 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
print("원소가 존재하지 않습니다")
else:
print(result + 1)
- 반복문을 이용한 구현
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1
return None
# n(원소의 개수)와 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None:
print("원소가 존재하지 않습니다")
else:
print(result+1)
- 실행 예
10 7 1 3 5 7 9 11 13 17 19 410 7 1 3 5 6 9 11 13 17 19 원소가 존재하지 않습니다.📝 Note! 문제의 경우 입력값이 오름차순으로 주어졌기 때문에 정렬하지 않았지만 아닐경우 사전에 정렬이 필요함.