데이터 100만 건 탐색 시 연산 횟수 100만 회에서 20회로 99.9% 절감

Context

데이터 규모 증가에 따른 검색 성능 저하 문제 발생. 단순 순차 탐색 방식인 Linear Search는 데이터 양에 비례해 처리 시간이 증가하는 O(n)의 시간 복잡도 한계 보유.

Technical Solution

• 정렬된 데이터셋을 전제로 탐색 범위를 매 단계 절반으로 축소하는 Binary Search 도입
• 중간값(Mid)과 타겟 값을 비교하여 탐색 윈도우를 좌측 또는 우측으로 재설정하는 분할 정복 로직 적용
• 대규모 배열 처리 시 발생 가능한 Integer Overflow 방지를 위해 left + (right - left) / 2 계산식 채택
• 읽기 작업 빈도가 높은 환경에서 검색 효율을 극대화하는 O(log n) 구조 설계
• 데이터 수정 시 발생하는 O(n)의 Shift 비용과 검색 이득 사이의 Trade-off 분석을 통한 최적 알고리즘 선택

Impact

• 데이터 1,000건 기준: 최대 1,000단계에서 약 10단계로 연산 횟수 단축
• 데이터 1,000,000건 기준: 최대 1,000,000단계에서 약 20단계로 연산 효율 극대화

Key Takeaway

알고리즘 선택 시 단순 검색 속도가 아닌 Read/Write 비율에 따른 전체 생명주기 비용을 고려한 설계 필요