이진 탐색
작성 완료
- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
- 처음 중간의 값을 임의의 값으로 선택하고 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용
- 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며 작으면 그 값은 새로운 최솟값이 됨
- 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점 ---> $O(logN)$
- 참고: 이진 탐색
def binary_search(arr, target):
arr.sort() ## 리스트를 오름차순으로 정렬
low = 0
high = len(arr) - 1 ## arr의 첫번째 인덱스(low)부터 마지막 인덱스(high)까지 탐색
while low <= high:
mid = (high + low) // 2
print('low: {}\nhigh: {}\nmid: {}'.format(low, high, mid))
if arr[mid] == target: ## 원하는 값을 찾으면 mid(인덱스)를 반환
return mid
elif arr[mid] > target: ## 원하는 값이 중간점보다 작은 경우 왼쪽 부분 탐색
high = mid - 1
else:
low = mid + 1 ## 원하는 값이 중간점보다 큰 경우 오른쪽 부분 탐색
return False ## 원하는 값이 arr에 없는 경우
arr = list(range(1, 101))
target = 88
binary_search(arr, target)
- 우리가 찾는 target인 88은 arr의 87번째 인덱스 값이라고 한다
arr[87]
- 진짜임
- 어떤 과정을 거쳐서 87번째 인덱스라는 것을 알려준 것일까?
- arr은 1부터 100까지의 값임
1. 1 2 3 $\cdots$ 98 99 100 ---> low는 0이고 high는 99이므로 mid는 49임
2. arr[mid(49)] = 50는 target(88)보다 작으므로 arr[mid(49)+1] ~ arr[high(99)] 를 탐색하면 target(88)이 존재할 것임
3. 51 52 53 $\cdots$ 98 99 100 ---> low는 50이고 high는 99이므로 mid는 74임
4. arr[mid(74)]는 target(88)보다 작으므로 arr[mid(74)+1] ~ arr[high(99)] 를 탐색하면 target(88)이 존재할 것임
5. 76 77 78 $\cdots$ 98 99 100 ---> low는 75이고 high는 99이므로 mid는 87임
6. arr[mid(87)]는 target(88)과 동일하므로 mid(87)를 return한다
- 시간 복잡도는 $O(logN)$이다
- 위에서 1~100사이에서 target을 찾는 과정을 살펴봤음
- 탐색 범위를 $N$이라고 한다면 처음에는 $N$만큼 탐색함
- 그 다음에는 $\frac{N}{2}$만큼 탐색함
- 또 그 다음에는 $\frac{N}{4}$만큼 탐색함
- 이를 살펴보면 탐색 범위는 $N, \frac{N}{2}, \frac{N}{4}, \cdots , 1$
- 시간 복잡도는 알고리즘의 의해 수행되는 기본 연산의 개수를 보면 알 수 있음
- 연산 횟수(탐색 반복 횟수)를 $k$라고 하면 처음 탐색($k=1$)때의 탐색 범위는 $N$, 두번째 탐색($k=2$)때의 탐색 범위는 $\frac{N}{2}$이며 이를 계속하면 탐색 범위는 $1$이 됨
- 위의 관계식을 통해 $N\times(\frac{1}{2})^{k} = 1$임을 알 수 있고 이를 정리하면 $k=log_{2}N$임
- Big O 표기법에서 로그의 밑은 영향이 없으므로 이진 탐색의 시간 복잡도는 $O(logN)$이라고 할 수 있음 ---> 이해 안되면 통계수학 big O 표기법 다시 보기