피드로 돌아가기
Dev.toBackend
원문 읽기
Binary Search 기반 분할 설계를 통한 O(log(min(m,n))) 시간 복잡도 달성
Median of Two Sorted Arrays — LeetCode #4 (Hard)
AI 요약
Context
두 개의 정렬된 배열을 결합하여 중앙값을 찾는 문제에서 단순 Merge 방식은 O(m+n)의 시간이 소요됨. 전체 데이터를 정렬하거나 합치는 과정에서 발생하는 불필요한 연산을 제거하고 로그 시간 복잡도를 달성해야 하는 제약 조건이 존재함.
Technical Solution
- 전체 데이터의 절반을 나누는 Dividing Line 개념을 도입하여 Merge 과정 없이 중앙값 탐색
- 작은 배열을 기준으로 Binary Search를 수행하여 탐색 범위를 매 단계 절반으로 축소
- 두 배열의 분할 지점 합계를 고정하여 한 쪽의 Cut 위치 결정 시 다른 쪽 위치가 자동 확정되는 구조 설계
- 분할 지점의 경계값 4개(left1, right1, left2, right2)를 비교하여 모든 왼쪽 값이 오른쪽 값보다 작거나 같은지 검증
- 인덱스 범위 초과 발생 시 Negative/Positive Infinity를 할당하여 Edge Case 처리 로직 단일화
- 입력 배열 중 크기가 더 작은 배열을 탐색 대상으로 선정하여 불필요한 Out-of-bounds 및 연산 횟수 방지
실천 포인트
1. O(log N) 요구사항 확인 시 Binary Search 적용 가능 여부를 우선 검토할 것
2. 두 개 이상의 정렬된 집합을 다룰 때, 상대적 크기에 따른 제약 조건을 활용해 탐색 범위를 최소화할 것
3. 경계값 처리 시 sentinel value(Infinity)를 활용해 조건문 분기를 단순화할 것