삼진 탐색 (Ternary search)

알고리즘 과목에서 과제로 나왔던 문제 중의 하나이다. 삼진 탐색 알고리즘을 짜라는 것이었는데 이진 탐색 알고리즘이야 이미 알고 있으니 매우 간단한 문제였다. 계속 응용하면 n진 탐색 알고리즘을 계속 만들 수 있다.

삼진 탐색 알고리즘의 시간복잡도는 O(log_3 n)인데 이진 탐색보다 빨라 보이지만 사실 따지고 보면 이진 탐색보다 느리다고 한다. 그래서 안 배우고 안 쓰는 듯... 하긴 더 빠르면 이걸 쓸 게 아니라 십진 탐색 알고리즘 같은 걸 쓰고 있었겠지...

찾아보니 단봉 함수의 최대/최소 값을 구할 때 삼진 탐색 알고리즘을 활용한다고 한다. 이건 나중에 알아봐야겠다.

int ternarySearch(int arr[], int key, int low, int high)
{
	int mid1, mid2;
	if (low > high)
	{
		return -1;
	}
	else
	{
		mid1 = low + (high - low) / 3;
		mid2 = high - (high - low) / 3;
		if (arr[mid1] == key)
		{
			return mid1;
		}
		else if (arr[mid2] == key)
		{
			return mid2;
		}
		if (key < arr[mid1])
		{
			return ternarySearch(arr, key, low, mid1 - 1);
		}
		else if (key > arr[mid2])
		{
			return ternarySearch(arr, key, mid2 + 1, high);
		}
		else
		{
			return ternarySearch(arr, key, mid1 + 1, mid2 - 1);
		}
	}
}