이진 탐색 binary search 파이썬 알고리즘
#이진탐색 #binary_search #Python #파이썬 #알고리즘
이진 탐색
이진 탐색binary search이란 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 또한 이진 탐색은** 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없고, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. 이진 탐색은 위치를 나타내는 **3개의 변수(시작점start, 끝점end, 중간점mid)을 사용한다. 매번 찾으려는 데이터와 중간점mid** 위치의 데이터를 반복적으로 비교**해서 원하는 데이터를 찾는다.
이진 탐색은 재귀 함수 혹은 반복문으로 구현할 수 있다.
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
28
# Python code
# 재귀 함수로 구현한 이진 탐색
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(찾고자 하는 문자열)을 입력받기 -> 7 3
n, target = list(map(int, input().split()))
# 전체 원소 입력받기 -> 2 3 4 6 8 10 15
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력 -> 2
result = binary_search(array, target, 0, n-1)
if result == None:
print("원소가 존재하지 않음")
else:
print(result + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Python code
# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
while start target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1
return None
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기 -> 7 3
n, target = list(map(int, input().split()))
# 전체 원소 입력받기 -> 2 3 4 6 8 10 15
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력 -> 2
result = binary_search(array, target, 0, n-1)
if result == None:
print("원소가 존재하지 않음.")
else:
print(result + 1)
시간 복잡도
이진 탐색의 시간 복잡도는 O(logN)이다. *여기서 로그는 당연히 밑을 2로 가지는 log2N이다. *당연히 사용할 수만 있다면(정렬되어 있다면) 순차 탐색 O(N)보다 이진 탐색 O(logN)이 빠르다.
언제 사용할까?
이진 탐색은 문제 탐색 범위가 큰 상황에서 효과적이고, 이런 상황에서 사용하도록 의도하고 코딩테스트 문제가 출제된다고 한다. 따라서 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근해보는 것이 좋다고 한다.
코딩 테스트 외의 상황에서는 데이터베이스에서의 탐색에서 이진 탐색이 유용하다. 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리Tree** 자료구조를 이용하여 항상 데이터가 정렬**되어 있다.
트리 구조란?
- 트리는 부모 노드와 자식 노드의 관계로 표현.
- 트리의 최상단 노드를 루트 노드라고 함.
- 트리의 최하단 노드를 단말 노드라고 함.
- 트리에서 일부를 떼어내도 트리 구조이며, 이를 서브 트리라고 함.
- 트리는 파일 시스템과 같이 '계층적이고 정렬된 데이터'를 다루기에 적합함.
- 부모 노드보다 왼쪽 자식 노드가 작다.
- 부모 노드보다 오른쪽 자식 노드가 크다.
이 글의 내용이 많은 도움이 된다면 아래 책을 사서 읽어보고 공부하는 것을 추천한다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
1
2
3
4
5
6
저자
나동빈
출판
한빛미디어
발매
2020.08.05.