[C] 삼분 탐색(Ternary Search)과 이진 탐색(Binary Search)

이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다

다음과 같은 코드를 사용한다

 

int biSearch(int l, int r, int target)
{
    // list에서 target 찾기
    int mid;
    while (l < r)
    {
        mid = (l + r) / 2;
        if (list[mid] < target)
            l = mid + 1;
        else
            r = mid;
    }
    //return idx값
    return r; //or l
}

 

다음은 이진 탐색을 이용한 알고리즘이다

- snupi.tistory.com/71

[백준 12015번][C] 이진 탐색(Binary Search)을 이용한 LIS(최장 증가 수열)

- snupi.tistory.com/62

[Java code] 이진 탐색(Binary Search) - 선형 이하 시간(Sublinear Time) 알고리즘

 

---

 

삼분 탐색(Ternary Search) 역시 이분할 대신 삼분할을 이용하는 방법이다

 

이진 탐색이 target을 가지고 범위를 반으로 줄여나가며 찾는 방법이라면,

삼분 탐색은 아래 조건일 때, 극대점 혹은 극소점을 찾아나가는 방법이다

 

조건 1) 하나의 지역에 극대(소)점이 있다 (▶ unimodal 함수)

조건 2) 최대점 왼쪽은 순증가(순감소) / 오른쪽은 순감소(순증가) (▶ 평평한 구간이 있는 단조증가(감소)는 X)

 

함수를 직접 미분하지 못할 때에도 사용할 수 있으며,

국소 탐색에 비해 빠르게 동작하고 수렴 판정이 용이하다

 

코드는 다음과 같이 이용된다

 

double f(double x);

double ternary(double lo, double hi)
{
    for(int iter=0 ; iter < 100 ; iter++) //100번만 하면 충분히 근사한 값을 얻는다
    {
        double a = (2*lo + hi) / 3.0;
        double b = (lo + 2*hi) / 3.0;
        if(f(a) > f(b))
            hi = b;
        else
            lo = a;
    }
    return (lo + hi) / 2.0;
}