이분 탐색 (Parametric Search)

2020. 7. 22. 23:48Algorithm/basic

이분 탐색 알고리즘

수열 또는 정렬된 배열에서 주어진 기준값에 근접한 값, 즉 정답을 구하기 위해 범위를 반으로 줄여나가며 정답을 구하는 알고리즘이다. 

본 알고리즘에서는 범위를 지정하는 시작점(left, start, low, ...)끝점(right, end, high, ...) 을 관리하는 두 가지 변수가 있다. 중앙값 mid는 수열에서는 중앙값, 배열에서는 중앙에 위치(인덱스와 관련)한 값이 된다. 이제 기준값을 중앙값 또는 중앙값으로 도출된 값, 즉 기준값과 비교한다.

1. 중앙값이 기준값보다 작을 경우

시작점(left, start, low, ...)을 [중앙값 또는 중앙 인덱스 + 1] 값으로 바꾼다.  

2. 중앙값이 기준값보다 클 경우

 끝점(right, end, high, ...)을 [중앙값 또는 중앙 인덱스 - 1] 값으로 바꾼다.  

언제 이분 탐색을 쓸까?

문제에서 구해야하는 값과 그 값이 포함된 수열 또는 배열과 같은 범위가 주어진다. 기준 점(X)를 통해 가능성 여부를 따져서 정답을 찾아낸다.

'Algorithm > basic' 카테고리의 다른 글

[자료구조] MAXHEAP: 최대힙  (0) 2020.06.02