O(M×N) 전수 조사를 O(log(M×N)) Binary Search로 최적화

Context

정렬된 2D Matrix 구조에서 특정 Target 값을 찾는 문제 상황. 모든 셀을 탐색하는 Brute Force 방식의 높은 시간 복잡도로 인한 성능 저하 발생.

Technical Solution

• Row 간 연속적 정렬 속성을 활용한 2D Matrix의 1D Array 가상화 설계
• 가상 인덱스 mid를 2D 좌표로 변환하는 row = mid / cols 및 col = mid % cols 연산 적용
• 전체 데이터셋에 대한 글로벌 정렬 상태를 활용한 Binary Search 알고리즘 도입
• inclusive search range 설정을 통한 경계값 누락 방지 및 정확한 탐색 범위 보장
• 포인터 기반의 탐색 범위 축소로 불필요한 연산 제거