이분탐색 (binary search) / 파라메트릭 서치 (parametric search)

이분탐색

[조건]

• 데이터가 정렬 되어있어야 함
• N개의 데이터 중 원하는 값을 찾을 때, O(logN)의 시간 내에 찾아야 하는 경우

[흐름]

• 정렬된 데이터의 start, last, mid(= (start + last) / 2 ) index를 설정
• target value와 정렬된 데이터의 mid index 값을 비교
  • target value > 데이터[index] 인 경우, start = mid+1로 설정
  • target value < 데이터[index] 인 경우, last = mid-1로 설정
  • target value == 데이터[index] 인 경우, 정답 찾음

 

 

파라메트릭 서치

[조건]

• 최소/최대 문제가 주어진 경우
• 주어진 값에 가까운 값을 구하는 경우
  • 이를 결정 문제로 변경 가능 => 이분 탐색 적용

주어진 최소/최대 값 찾기 문제를 이분 탐색에 맞게 재 정의하는 과정이라고 이해