배열 X 와 Y 의 모든 2n 개 요소 의 중위 수 를 찾 아 라.

알고리즘 서론 제3 판, 9.3 - 8
알고리즘:

두 배열 의 길이 가 1 이면 작은 것

을 선택한다.

그렇지 않 으 면 두 배열 의 중위 수 를 꺼낸다.

비교적 큰 중위 수 를 가 진 배열 의 낮은 구역 과 비교적 낮은 중위 수의 높 은 구역 을 취하 여 새로운 길이 가 n 인 배열 로 조합 했다.

새 배열 의 중위 수 를 찾 아 라

사고: 재 귀 치 료 를 하 는 이상 기본 적 인 상황 이 있 을 것 이다. 기본 적 인 상황 은 바로 배열 의 길이 가 1 이다. 관찰 하면 전체적인 중위 수 는 두 배열 의 중위 수 사이 에 있 는 것 을 발견 할 수 있다.상세 한 증명 은 다음 과 같다. 전체 중위 수 는 M 이 고 X 의 중위 수 는 MX 이 며 Y 의 중위 수 는 MY 이다. M 이 X (Y 와 유사) 에 있다 고 가정 하면 M 이 X 에서 의 좌 표 는 k 이다.

X + Y 에는 모두 n 개의 요소 가 M 보다 작 습 니 다. 그 중에서 X 는 k 개 를 기 여 했 고 Y 는 n - k 개 를 기 여 했 습 니 다.

X 에는 n / 2 개의 원소 가 MX 보다 작고 Y 에는 n / 2 개의 원소 가 MY

보다 작다.
상기 두 가지 점 에 따라 k < n / 2 라면 MY < M < MX, M 은 Y 의 높 은 구역 + X 의 낮은 구역 에 위치 합 니 다.만약 k ≥ n / 2 라면 MX < M < MY, M 은 Y 의 낮은 구역 + X 의 높 은 구역 에 위치한다.다시 말 하면 어떤 경우 에 도 전체 중위 수 는 비교적 큰 중위 수 를 가 진 배열 의 낮은 구역 과 비교적 낮은 중위 수 배열 의 높 은 구역 으로 구 성 된 새로운 배열 에 위치 해 있다.
Python 코드 는 다음 과 같 습 니 다:

def two_array_median(a, b):
    if len(a) == 1:
        return min(a[0], b[0])

    m = median_index(len(a))
    i = m + 1
    if a[m] < b[m]:
        return two_array_median(a[-i:], b[:i])
    else:
        return two_array_median(a[:i], b[-i:])

def median_index(n):
    if n % 2:
        return n // 2
    else:
        return n // 2 - 1

영문 참조 연결http://clrs.skanev.com/09/03/08.html