이진 탐색
이진 탐색
정렬된 리스트에서 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하는 알고리즘
따라서 이분 탐색을 하기 전에 필수적으로 리스트를 정렬시켜줘야한다.
기본적인 코드는 다음과 같다.
재귀 함수로 구현
1
2
3
4
5
6
7
8
9
10
def binary_search(arr, target, start, end):
if start > end: # 데이터를 못찾았을 경우
return None
mid = (start+end)//2
if arr[mid] == target:
return mid
elif arr[mid] < target: # target이 mid의 데이터보다 클 경우
return binary_search(arr,target,mid+1,end)
else: # target이 mid의 데이터보다 작은 경우
return binary_search(arr,target,start,mid-1)
반복문으로 구현
1
2
3
4
5
6
7
8
9
10
def binary_search(arr,target,start,end):
while start <= end:
mid = (start+end)//2
if arr[mid] == target:
return mid
if arr[mid] < target: # target이 mid의 데이터보다 클 경우
start = mid + 1
else: # target이 mid의 데이터보다 작은 경우
end = mid -1
return None
백준 - 수 찾기
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = int(input())
arr_n = list(map(int, input().split()))
m = int(input())
arr_m = list(map(int, input().split()))
arr_n.sort()
def binary_search(arr,target,start,end):
while start <= end:
mid = (start+end)//2
if arr[mid] == target:
return 1
elif arr[mid] < target:
start = mid + 1
else:
end = mid - 1
return 0
for i in arr_m:
print(binary_search(arr_n,i,0,n-1))
아주 기본적인 이진 탐색 문제이다. target을 찾으면 1을 출력하고, 못찾으면 0을 출력하도록 한다.
이진 탐색을 이용하지 않은 정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
arr_n = list(map(int, input().split()))
m = int(input())
arr_m = list(map(int, input().split()))
arr_n.sort()
for i in range(m):
if arr_m[i] in arr_n:
print(1)
else:
print(0)
사실 처음 풀 때는 이진 탐색을 몰랐기 때문에, if <target> in arr 를 이용하여 풀었는데 통과되었다.
하지만 이렇게 풀면 시간이 4928ms가 소요되고, 이진 탐색을 풀었을 때는 20배 가까이 짧은 244ms이 소요된다.
백준 - 숫자 카드
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = int(input())
arr_n = list(map(int, input().split()))
m = int(input())
arr_m = list(map(int, input().split()))
arr_n.sort()
count = {}
for i in arr_n: # arr_n을 순회하면서 count 딕셔너리를 이용하여 해당 숫자의 개수를 센다.
if i in count:
count[i] += 1
else:
count[i] = 1
def binary_search(arr,target,start,end):
if start > end:
return 0 # 못찾았으면 개수 0 반환
mid = (start+end)//2
if arr[mid] == target:
return count[target] # 찾으면 count, 즉 개수를 반환
elif arr[mid] < target:
return binary_search(arr,target,mid+1,end)
else:
return binary_search(arr,target,start,mid-1)
for i in arr_m:
print(binary_search(arr_n,i,0,n-1), end=' ')
이진 탐색은 개수를 세는 역할이 없기 때문에, 개수는 따로 세어주고, 해당 숫자가 리스트에 존재하는지를 이진 탐색으로 확인해준다.
이진 탐색을 이용하지 않은 정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
arr_n = list(map(int,input().split()))
m = int(input())
arr_m = list(map(int,input().split()))
arr_n.sort()
count={}
for card in arr_n:
if card in count:
count[card] += 1
else:
count[card] = 1
for i in arr_m:
if i in count:
print(count[i], end=" ")
else:
print(0,end=' ')
이 문제는 이진 탐색을 이용하지 않고 푸는 것이 더 빠르다.
이진 탐색 이용 o (재귀문) : 1652ms
이진 탐색 이용 o (반복문) : 896ms
이진 탐색 이용 x : 640ms
첫 번째 코드는 count 딕셔너리에 직접 조회하지만, 두 번째 코드는 여러 번의 이진 검색을 arr_n에서 실행하기 때문에 오버 헤드가 발생한다. 탐색할 때는 효율적이지만, 빈도수를 계산할 때는 딕셔너리를 이용하는 것이 더 효율적이다.