이분 사상 과 분 치 법

이분 사상 과 분 치 법
만약 에 개념 에 민감 하 다 면 이 두 가지 작은 차이 점 을 바로 깨 닫 게 될 것 이다. 2 분 검색 은 매번 절반 을 버 리 고 남 은 절반 에서 목 표를 찾 아야 한다.한편, 분 치 법 은 하나의 큰 문 제 를 두 개 또는 여러 개의 작은 문제 로 나 누 어 이런 작은 문제 들 의 해 를 재 귀적 으로 구하 고 마지막 으로 그들 을 조 심 스 럽 고 신중하게 합병 시 키 며 합병 할 때 발생 하 는 새로운 상황 을 자세히 고려 해 야 한다.물론 잘못 은 없 지만, 너 도 곧 이곳 에서 이들 의 큰 관 계 를 깨 닫 게 될 것 이다.배열 에서 k 번 째 가장 작은 숫자 를 선택 한 알고리즘 에 있어 서 하나의 버 전 은 빠 른 정렬 에서 수정 한 것 이다. 구분 한 후에 존재 하지 않 는 구간 을 버 리 고 나머지 부분 에 대한 교체 (후 문 은 설명 할 것 이다) 이 고 빠 른 순 서 는 분 치 법의 전형 적 인 대표 이다.
정식으로 이 문 제 를 다음 과 같이 서술 하 다.
O (n) 시간 내 에 배열 x [0... n - 1] 에서 K 의 가장 작은 요 소 를 찾 아 냅 니 다.원 배열 의 요소 위 치 를 바 꿀 수 있 습 니 다.
다음 코드 는 빠 른 정렬 에서 수정 되 었 고 무 작위 로 요 소 를 구분 하 는 문 제 를 고려 하 였 습 니 다.

int partition(int *array, int p, int r) {
    int x,i,j;
    x = array[r];
    i = p-1;
    for (j=p;j<=r-1;j++) {
        if (array[j]<= x) {
            i++;
            swap_value(array+i,array+j);
        }
    }
    swap_value(array+i+1,array+r);
    return i+1;
}


int random_select(int *array, int p, int r, int i) {
    int q,k;
    if (p == r)
        return array[p];
    q = random_partition(array,p,r);
    k = q-p+1;
    if (i == k)
        return array[q];
    else if (i

 
확장: (< 계속 > 연습 문제 15.2) 어떻게 3 원 배열 에서 두 번 째 작은 것 을 선택 합 니까?1000000 개 중 1000 개의 최소 요 소 를 선택 하고 테이프 에 입력 하면?
분석: 전 자 는 기껏해야 3 번 만 비교 하면 된다. 1 과 2, 1 과 2 중 가장 큰 것 과 3, 1 과 2 중 가장 작은 것 과 3.후 자 는 옮 겨 다 닐 때 1000 크기 의 최대 더미 로 현재 가장 작은 1000 개 를 저장 하면 된다.사실은 전 자 는 문 제 를 몇 단계 만 있 으 면 해결 할 수 있 고 복잡 한 재 귀 함 수 를 사용 할 필요 가 없 으 며 직접 풀 면 된다 는 것 을 설명 하기 위해 서 이다.후 자 는 테이프 가 랜 덤 I / O 를 하 는 것 이 불편 하기 때 문 입 니 다. 그렇지 않 으 면 K = 1001 로 구분 하면 K 앞의 1000 개가 원 하 는 요소 입 니 다.