Modified Binary Search를 통한 Rotated Sorted Array 탐색 시간 복잡도 O(log N) 달성

Context

전체 정렬 상태가 깨진 Rotated Sorted Array 환경에서 Target 값을 탐색해야 하는 문제 상황. 순차 탐색 방식의 O(N) 시간 복잡도로 인한 대규모 데이터셋 처리 효율성 저하가 주요 한계점.

Technical Solution

• 회전된 배열에서도 최소 한 개의 부분 배열은 항상 정렬 상태를 유지한다는 속성을 활용한 Search Space 분할
• mid 지점을 기준으로 좌우 구간 중 정렬된 구간을 우선적으로 식별하는 분기 로직 설계
• 식별된 정렬 구간의 범위(Low/High)와 Target 값을 대조하여 탐색 대상 구간을 결정하는 필터링 적용
• Target이 정렬 구간 내에 존재하지 않을 경우 반대편 비정렬 구간으로 탐색 범위를 즉시 이동시키는 최적화
• 매 반복마다 탐색 공간을 50%씩 제거하여 로그 시간 복잡도를 유지하는 Modified Binary Search 구조 구현