이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.
이진 검색은 먼저 배열의 중앙에 위치한 원소에 주목한다. 중앙 원소와 Key(검색하고자 하는 값)을 비교하며, 검색 범위를 좁혀가며 탐색을 진행한다.
맨 앞, 맨 끝, 중앙의 인덱스를 각 각 low, mid, high라고 해보자.
1) mid 값이 Key(검색하고자 하는 값)보다 작은 경우
- mid 값 포함 하위 값을 검색 범위에서 제외
- low = mid + 1
2) mid 값이 Key(검색하고자 하는 값)보다 큰 경우
- mid 값 포함 상위 값을 검색 범위에서 제외
- high = mid = 1
3) mid 값이 Key(검색하고자 하는 값)과 같은 경우
- 값을 찾았으므로 종료
이진 탐색 구현
from typing import Sequence, Any
def bin_search(a :Sequence, key: Any) -> int:
pl = 0
pr = len(a) - 1
while (pl <= pr):
pc = (pl + pr) // 2
if a[pc] < key:
pl = pc + 1
elif a[pc] > key:
pr = pc - 1
else:
return pc
return -1
if __name__ == '__main__':
num = int(input("원소의 개수를 입력하세요 : "))
arr = [None] * num
arr[0] = int(input(f"arr[0]의 값을 입력하세요 : "))
for i in range(1,num):
arr[i] = int(input(f"arr[{i}]의 값을 입력하세요 : "))
if arr[i-1] > arr[i]:
break
key = int(input("검색하고 싶은 값을 입력하세요 : "))
result = bin_search(arr, key)
if result == -1:
print("값을 찾지 못했습니다.")
else:
print(f"{key} 값은 배열의 {result} 인덱스에 존재합니다.")시간 복잡도
이진 탐색은 최악의 경우 남은 데이터가 하나가 될 때까지 탐색을 반복한다. 이를 고려해 시간 복잡도를 계산할 수 있다.
전체 데이터의 수를 이라고 하자.
1 -> 첫 번째 탐색 후 절반만 남아 남은 데이터 수 = =개.
2 -> 두 번째 탐색에서 다시 절반만 남은 데이터 수 = =개.
3 -> 세 번째 탐색에서 다시 절반이 남아 남은 데이터 수 = 개.
k ->규칙을 찾아보면 k번째 탐색에서 남은 데이터 수 = 이 된다.
최악의 경우에선이 될 때까지 탐색을 하게 된다.
위 식의 양변에 를 곱하면 가 되고 다시 양변에 를 취하면 최종 식은 이 된다.
여기서 k는 탐색 횟수로 N에 따라 시행 횟수는 이 된다. 따라서 시간 복잡도는 으로 나타낼 수 있다.
반응형
'Algorithm' 카테고리의 다른 글
| [Python] 선형 검색 (1) | 2022.10.08 |
|---|