피드로 돌아가기
Dev.toBackend
원문 읽기
O(log(min(N,M))) 시간 복잡도를 달성한 Binary Search 기반 Partition 설계
kth smallest element in sorted array
AI 요약
Context
두 개의 정렬된 배열에서 k번째 최솟값을 찾는 문제로, 단순 Merge 방식의 O(N+M) 시간 및 공간 복잡도 한계 존재. 데이터 규모 증가에 따른 선형 탐색의 비효율성을 해결하기 위한 로그 시간 복잡도 설계 필요.
Technical Solution
- 두 배열의 크기 차이를 고려한 작은 배열 기준의 Binary Search 수행을 통한 탐색 범위 최적화
- 전체 k개 요소가 좌측 영역에 배치되도록 하는 cut1, cut2 분할 지점 정의
- left1 ≤ right2 및 left2 ≤ right1 조건을 통한 Partition의 유효성 검증 로직 구현
- 유효 Partition 확인 시 max(left1, left2)를 통해 k번째 요소 확정하는 구조 설계
- 배열 경계값 처리 위해 Integer.MIN_VALUE 및 MAX_VALUE를 활용한 예외 케이스 방어
- 불필요한 메모리 할당을 배제한 In-place 포인터 조작 방식 채택
실천 포인트
1. 두 정렬 배열 대상의 탐색 문제 시 Binary Search on Partition 적용 가능성 검토
2. 시간 복잡도 개선을 위해 더 작은 입력 배열을 기준으로 탐색 범위 설정
3. 인덱스 범위 초과 방지를 위한 Boundary Value 처리 전략 수립