이진 탐색, 이분 탐색(binary search)이란?
말 그대로 이등분 해가며 탐색하는 알고리즘이다.
찾아야할 숫자가 100이라면
1부터 100까지 하나씩 찾아가는 선형 탐색에 비해
이분 탐색을 활용해
이등분씩 해나가며 탐색을 하면 시간복잡도를 훨씬 줄일 수 있다.
이분 탐색 기본 코드 예제
def binary_search(array: list, target: int):
left = 0
right = len(array) - 1
while left <= right:
mid = (left + right) // 2
if array[mid] > target:
right = mid - 1
elif array[mid] < target:
left = mid + 1
else:
return 1
return 0
array의 길이를 기준으로 왼쪽과 오른쪽을 나누고 array의 중간 값과 target 값을 비교해
크다면 오른쪽으로 작다면 왼쪽으로 다시 이등분 해주는 식이다.
# 심화
def recursive_binary_search(array, left, right, target):
if left > right:
return 0
mid = (left + right) // 2
if array[mid] > target:
right = mid - 1
elif array[mid] < target:
left = mid + 1
else:
return 1
return recursive_binary_search(array, left, right, target)
활용 예제 코드
input()
n = sorted(list(map(int, input().split())))
M = int(input())
m = list(map(int, input().split()))
def zero_or_one(n, i):
left = 0
right = len(n) - 1
while left <= right:
mid = (left + right) // 2
if i > n[mid]:
left = mid + 1
elif i < n[mid]:
right = mid - 1
else:
return 1
return 0
for i in m:
print(zero_or_one(n, i))
'TIL > 자료구조 & 알고리즘' 카테고리의 다른 글
자료구조의 유형 (1) | 2024.03.22 |
---|---|
파이썬으로 Heap 구현하기 (0) | 2024.03.19 |
파이썬으로 stack 구현하기 (0) | 2024.03.15 |
깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) (0) | 2024.03.11 |
배열(array)과 연결리스트(linked list) 차이점 (0) | 2024.03.04 |