Chapter. 3

4. 이분탐색과 파라매트릭 서치

이분 탐색(Binary Search)은 이름에서 부터 알 수 있듯이 2개로 나누는 탐색 방법입니다.

아마 술자리에서 업다운 을 해보신 분들은 익숙한 알고리즘일수도 있습니다. 정렬 전처리를 필요로 하며, 다음과 같은 과정을 거칩니다.

  1. 정렬 여부 확인 및 정렬
  2. 시작점과 끝점 확인 (lo, hi 또는 st, ed 또는 l, r 표현)
  3. 시작점과 끝점의 중간 포인트 산술 평균 계산 ((lo + hi) // 2)
  4. 중간 포인트에서 결과와 찾고자 하는 결과 비교
  5. 비교에 따라 시작점이나 끝점을 중간점으로 변경
  6. 결론적으로 범위가 1/2로 줄어들며 탐색
  7. 최후에 1개가 남으면 결과가 확정

간단하게 코드로 작성하면 다음과 같습니다.

def binary_search(lst, value, N):
    lo, hi = 0, N-1
    while lo <= hi :
        mid = (lo + hi) // 2
        if lst[mid] == value : return mid
        if lst[mid] < value : lo = mid+1
        else : hi = mid-1
    return False

보통 3가지 방법으로 사용합니다. 과정은 거의 유사하나 task에 따라 적재적소에 사용하면 됩니다.

  • 존재 유무 확인
  • lower bound : 찾고자 하는 값 이상이 처음 나타나는 위치
  • upper bound : 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치

이를 활용하면 조금 어렵지만 이런 문제를 해결할 수 있습니다.

bisect.bisect 라이브러리 사용 가능

이분 탐색의 조금 심화된 버전으로 보면 됩니다.

4-3은 교양 알고리즘 지식으로 알아두면 좋습니다. 종종 대회에는 사용하는 알고리즘이기도 하나 메이저한 알고리즘은 아닙니다.

삼분 탐색은 상태를 3개로 나누어서 살펴보는 방법입니다. 흔히 상태가 오목/볼록 그래프일때 사용합니다.