3 분 찾기

개념
2 분 검색 을 바탕 으로 오른쪽 구간 (또는 왼쪽 구간) 에서 2 분 을 더 진행 합 니 다. 이러한 검색 알고리즘 은
3 점 찾기, 즉 3 점 법.
3 분 검색 은 보통 가장 가 치 를 신속하게 확정 하 는 데 쓰 인 다.
2 분 검색 대상 검색 서열 에 대한 요 구 는 단조 성 (엄격 하고 단조 로 운 것 은 아니다) 이다.단조 로 운 서열 이 없 는 것 은 2 점 으로 찾 는 것 이 아니다.
2 분 검색 과 달리 3 분 법 이 대상 으로 하 는 검색 서열 에 대한 요 구 는 다음 과 같다.
서열 은 돌출 함수 이다.쉽게 말 하면 이 서열 은 반드시 최대 치 (또는 최소 치) 가 있어 야 하고 최대 치 (최소 치) 의 왼쪽 서열 은 엄격 하지 않 고 단조 로 운 증가 (감소) 를 만족 시 켜 야 하 며 오른쪽 서열 은 엄격 하지 않 고 단조 로 운 감소 (증가) 를 만족 시 켜 야 한다.다음 그림 은 최대 값 의 돌출 함 수 를 나타 낸다.
2. 알고리즘 과정
(1) 이분법 과 유사 하여 전체 구간 의 중간 값 mid 를 먼저 취한 다.
 

mid = (left + right) / 2;

(2) 오른쪽 구간 의 중간 값 midmid 를 취하 여 구간 을 세 개의 동네 로 나눈다.
 
4. 567913. (3) 우리 mid 는 midmid 보다 가장 가 깝 습 니 다. 우 리 는 오른쪽 구간 을 버 립 니 다. 그렇지 않 으 면 우 리 는 왼쪽 구간 을 버 립 니까?
mid 와 midmid 가 가장 가 까 운 값 을 비교 하려 면 mid 가 있 는 함수 값 과 midmid 가 있 는 함수 값 의 크기 만 확인 해 야 합 니 다.가장 값 이 최대 치 일 때, mid 와 midmid 중 비교적 큰 것 은 자연히 가장 가 까 워 진다.최 치가 최소 일 때 는 동일 하 다. 

midmid = (mid + right) / 2;

(4), 최 치 를 찾 을 때 까지 반복 (1) (2) (3).
(5) 다른 3 분 표기 법

if (cal(mid) > cal(midmid))
    right = midmid;
else
    left = mid;

 
알고리즘 의 정확성:
1. mid 와 midmid 는 가장 값 이 같은 쪽 에 있 습 니 다.볼록 함 수 는 최대 치 (최소 치) 의 임의의 측면 에서 단조 성 을 가지 기 때문에 mid 와 midmid 중에서 더 큰 (작은) 의 그 수 는 자연히 가장 가 까 워 진다.이때 우 리 는 가장 값 진 구간 에서 가장 값 진 구간 을 포함 할 수 없 기 때문에 버 릴 수 있다.
2、
mid 와 midmid 는 가장 값 진 양쪽 에 있 습 니 다.가장 값 이 중간의 한 구간 에 있 기 때문에, 우 리 는 한 구간 을 버 린 후, 결코 가장 값 에 영향 을 주지 않 을 것 이다.

double three_devide(double low,double up)
{
    double m1,m2;
    while(up-low>=eps)
    {
        m1=low+(up-low)/3;
        m2=up-(up-low)/3;
        if(f(m1)<=f(m2))
            low=m1;
        else
            up=m2;
    }
    return (m1+m2)/2;
}

ternary Search (0, 6) 를 호출 하여 되 돌아 온 결 과 는 3.0000 입 니 다.