이진탐색은 오름차순으로 정렬된 배열에서 원하는 숫자(Target)를 찾는 정렬 알고리즘입니다.
시간 복잡도는 항상
입니다. 그러므로 시간을 단축할 때 유용하게 사용할 수 있는 알고리즘입니다.
쉽게 이해할수 있게 이미지를 가져왔습니다.
말로 쉽게 표현을 하면 찾는 값(Target)과 중간 인덱스에 있는 값을 비교해서 찾는 값(Target)이 더 작으면 중간 인덱스 기준왼쪽 값과 비교를 하고 크면 오른쪽 값과 비교를 해서 점차 범위를 줄여 나가는 알고리즘입니다.
문제와 함께 설명하겠습니다.
https://www.acmicpc.net/problem/10815
10815번: 숫자 카드
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
이 문제는 이진 탐색이 아니더라도 쉽게 풀 수 있는 문제입니다.
하지만 이진 탐색 알고리즘을 사용하지 않으면 시간 초과가 되는 모습을 확인 할 수 있습니다.
우선 이진 탐색 알고리즘은 오름차순으로 정렬을 꼭! 해야 하기 때문에 문제에서는 상근이가 가지고 있는 카드를 입력받고
sort함수를 사용 해야합니다.
|
1
2
3
|
n = int(input())
card = list(map(int, sys.stdin.readline().split()))
card.sort()
|
cs |
여기서 N은 상근이가 가지고 있는 카드의 개수인데 파이썬에서는 list 형식으로 숫자를 입력받을 수 있기 때문에
N값을 사용하지 않습니다. 값을 받은 후 sort함수를 이용해 오름차순으로 정렬을 하였습니다.
그 후, 똑같은 방식으로 찾는 값(Target)을 입력받았습니다.
|
1
2
|
m = int(input())
check = list(map(int, sys.stdin.readline().split()))
|
cs |
밑의 코드는 이진 탐색 알고리즘을 이용해 반환값을 0 또는 1로 설정한 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
def binary_search(target,data,start,end):
while(start <= end):
mid = (start + end)//2
if data[mid] == target:
return 1
elif data[mid] < target:
start = mid + 1
else:
end = mid-1
return 0
|
cs |
코드를 설명하자면 우선 저는 While 반복문을 사용해 Start <= End 일 때 코드가 실행되게 하였습니다.
Start값이 End값보다 크면 시작 값이 끝 값보다 큰 경우이기 때문에 고려할 필요가 없어서 조건문을 사용하셔서 작은 경우만 고려하시면 됩니다.
그 후, mid = (start + end) //2를 이용해서 중간 값을 설정합니다.
중간 값과 찾는 값(Target)이 같으면 즉시 return 1을 해주며 반복문을 종료시킵니다.
만약 중간값이 찾는 값(Target) 보다 작으면 중간 값보다 더 큰 값에서 찾아야 하기 때문에 시작값(start)을 중간값에서 1을 더한 값으로 설정합니다.
이와 비슷한 원리로 중간 값보다 찾는 값(Target)이 더 작으면 끝 값(End)을 중간 값에서 1보다 작은 수로 설정합니다.
정답코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import sys
n = int(input())
card = list(map(int, sys.stdin.readline().split()))
card.sort()
m = int(input())
check = list(map(int, sys.stdin.readline().split()))
def binary_search(target,data,start,end):
while(start <= end):
mid = (start + end)//2
if data[mid] == target:
return 1
elif data[mid] < target:
start = mid + 1
else:
end = mid-1
return 0
for i in range(m):
print(binary_search(check[i],card,0,n-1),end=' ')
|
cs |