이진 탐색 - 두 개로 나눠서 탐색
이진 탐색(Binary Research)은 이분 탐색이라고도 불린다. 이진 탐색은 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식으로 동작한다. 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색하는데 사용되지만, 리스트, 트리 등에서도 사용할 수 있다.
하지만 모든 리스트, 트리에서 사용할 수 있는 것이 아니라 반드시 원소들이 일정한 순서(예를 들면 오름차순)로 정렬된 구조에서만 사용할 수 있기 때문에 정렬된 리스트나 트리에서 사용이 가능하다.
이진 탐색의 시간 복잡도는 O(log n)으로, 배열의 크기에 비례하여 실행 시간이 빨라진다. 따라서 대용량 데이터에서 특정 값의 위치를 찾는 데 용이하다.
배열에서의 동작 방식
1.
정렬된 배열에서 중간 인덱스(mid)를 찾는다. → (start + end)
2.
찾으려는 값(target)과 중간 값(mid_val)을 비교한다.
3.
target이 mid_val보다 작으면 mid를 기준으로 왼쪽 부분 배열을 탐색한다.
target이 mid_val보다 크면 mid를 기준으로 오른쪽 부분 배열을 탐색한다.
4.
탐색 범위를 반으로 줄인다.
5.
탐색 범위가 더 이상 없을 때까지 위 과정을 반복한다.
def binary_search(data, target):
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
if data[mid] == target:
return True
elif data[mid] < target:
start = mid + 1
else:
end = mid - 1
return -1
n = 7
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
binary_search(arr, n)
Python
복사
기본적인 이진 탐색 코드
트리에서의 동작 방식
1.
트리에서 중간 노드를 찾는다.
2.
찾으려는 값과 중간 노드의 값과를 비교한다.
3.
찾으려는 값이 중간 노드의 값보다 작으면 왼쪽 하위 트리에서 탐색을 계속한다.
찾으려는 값이 중간 노드의 값보다 크면 오른쪽 하위 트리에서 탐색을 계속한다.
4.
탐색 범위를 반으로 좁힌다.
5.
탐색 범위가 더 이상 없을 때까지 위 과정을 반복한다.
주의점!!
트리 구조에서 이진 탐색을 적용하기 위해서는, 탐색 대상이 되는 트리가 반드시 이진탐색 트리(Binary Search Tree) 구조를 가져야 한다.
이진 탐색 트리란?
각 노드가 하나의 키를 저장하고, 왼쪽 서브트리의 키는 부모 노드의 키보다 작고, 오른쪽 서브트리의 키는 부모 노드의 키보다 큰 이진트리의 형태이다.
파이썬 라이브러리 - bisect
bisect은 정렬된 리스트에서 특정 원소를 찾을 때 효과적으로 사용할 수 있는 라이브러리이다.
많은 메소드들 중 bisect_left, bisect_right를 사용하면 많은 문제들을 해결할 수 있다.
•
bisect_left(a, x): 배열 a의 정렬된 상태를 유지하면서 원소 x를 삽입할 수 있는 가장 왼쪽 인덱스를 리턴
•
bisect_right(a, x): 배열 a의 정렬된 상태를 유지하면서 원소 x를 삽입할 수 있는 가장 오른쪽 인덱스를 리턴
from bisect import bisect_left, bisect_right
Python
복사
정렬된 배열 array=[1, 2, 3, 4, 4, 6, 8, 9]가 있을 때, 4를 삽입할 수 있는 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 찾기 위해서는 다음과 같이 코드를 작성할 수 있다.
from bisect import bisect_left, bisect_right
array = [1, 2, 3, 4, 4, 6, 8, 9]
x = 4
print(bisect_left(array, x)) # 3
print(bisect_right(array, x)) # 5
Python
복사
설명
bisect_left와 bisect_right를 사용해 해당 배열에서 특정 범위에 포함되는 원소의 개수를 구할 수 있다.
from bisect import bisect_left, bisect_right
# 값이 [left, right] 범위에 있는 데이터의 개수를 반환하는 함수
def count_by_range(a, left, right):
right_index = bisect_right(a, right)
left_index = bisect_left(a, left)
return right_index - left_index
array = [1, 2, 3, 4, 4, 6, 8, 9]
# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(array, -1, 3))
Python
복사
설명
위 count_by_range 함수를 이용하면 배열 a에서 원소 x의 개수를 구할 수도 있다.
from bisect import bisect_left, bisect_right
# 값이 [left, right] 범위에 있는 데이터의 개수를 반환하는 함수
def count_by_range(a, left, right):
right_index = bisect_right(a, right)
left_index = bisect_left(a, left)
return right_index - left_index
array = [1, 2, 3, 4, 4, 6, 8, 9]
# 값이 4인 데이터 개수
print(count_by_range(a, 4, 4))
Python
복사
설명
파라메트릭 서치 (Parametric Search)
최적화 문제를 결정 문제(Yes or No)로 바꾸어 해결하는 기법.
특정 조건 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제에 사용됨.
특징
탐색 범위가 매우 크게 주어짐 O(n) 인 선형탐색으로는 시간초과 나는 경우 사용가능
정렬된 리스트에서 범위를 중간값으로 잘랐을때 특정 조건을 만족하는지 확인할 때 사용됨
구현
바이너리 서치 함수 안에서 중간값으로 잘랐을때 어떤 조건을 만족하는지 확인
