탐색 - Parametric Search

Parametric Search는 최댓값 혹은 최소값을 찾는 최적화 문제를 결정 문제로 변경하여 풀 수 있는 탐색 알고리즘 입니다. 전체 코드는 이진 탐색(Binary Search)과 매우 유사합니다. 주로 연속성이 있는 값들에서 특정 경계를 O(LogN)에 찾는 데 사용되는 알고리즘입니다.

Parametric Search

#include <stdio.h>

int data[10] = { -5, -1, -2, -10, 8, 1, 4, 10, 11, 8 };

// 입력으로 들어온 Index를 선택하면 양수인지 확인(결정)
bool isTrue(int idx) {
	if (data[idx] > 0) return true;
	else return false;
}

// 파라메트릭 서치
int parametricSearch(int start, int end) {
	int mid = (start + end) / 2;
	if (start == end) {
		return mid;
	}
	if (isTrue(mid)) {
		return parametricSearch(start, mid);
	} else {
		return parametricSearch(mid + 1, end);
	}
}

int main() {
	int idx = parametricSearch(0, 9);
	printf("Index: %d, Value: %d\n", idx, data[idx]);

}

출력

Index: 4, Value: 8