Binary Search 기반 Partition 설계를 통한 O(log(min(N,M))) 시간 복잡도 달성

Context

두 개의 Sorted Array에서 Median을 찾기 위해 전체 배열을 병합하는 Brute Force 방식을 검토함. 해당 방식은 O(N + M)의 시간 및 공간 복잡도를 요구하여 대규모 데이터셋 처리 시 리소스 효율성이 저하되는 한계 존재.

Technical Solution

• 전체 요소의 절반을 기준으로 Left Half와 Right Half를 분리하는 Partition 전략 채택
• 두 배열 중 길이가 짧은 배열을 대상으로 Binary Search를 수행하여 Search Space 최소화
• Left Half의 모든 요소가 Right Half보다 작거나 같도록 보장하는 Partition Point 탐색 로직 구현
• 각 배열의 분할 지점인 cut1, cut2를 설정하여 인접 요소 간의 교차 비교를 통한 최적 분할 지점 결정
• 분할 완료 후 요소 총합의 홀짝 여부에 따라 Max(Left) 또는 평균값을 반환하는 연산 처리
• 추가 메모리 할당을 배제한 In-place 연산으로 공간 효율성 극대화