[LeetCode][JAVA] 33. Search in Rotated Sorted Array

💡 문제
33. Search in Rotated Sorted Array (https://leetcode.com/problems/search-in-rotated-sorted-array/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

 

• 이진 탐색(Binary Search): 정렬 배열에서 O(log n)으로 탐색.
• 회전된 정렬 배열의 성질: 중복이 없으면 임의의 mid에서 좌/우 절반 중 하나는 반드시 오름차순이다.
• 구간 선택 불변식: 매 반복, “정렬된 절반”을 판별 → 타겟이 그 정렬 구간 범위에 포함되면 그쪽으로, 아니면 반대쪽으로 탐색 구간을 절반으로 줄인다.

 

---

🤓 문제 풀이

오름차순 정렬 배열이 어떤 피벗 k에서 회전된 상태에서, 주어진 target의 인덱스를 O(log n)에 찾아야 한다.
핵심은 매 스텝마다 정렬된 쪽을 판별하고, 타겟의 포함 여부로 탐색 구간을 절반으로 축소하는 것.

 

🔨 문제 설명

• 입력: nums(회전 가능 오름차순, 중복 없음), target
• 출력: target의 인덱스 (없으면 -1)

예)

• nums = [4,5,6,7,0,1,2], target = 0 → 4
• nums = [4,5,6,7,0,1,2], target = 3 → -1
• nums = [1], target = 0 → -1

제약

• 1 <= nums.length <= 5000
• 모든 값 고유(중복 없음)

---

🔨 접근 방법

1. lo=0, hi=n-1로 시작, mid = lo + (hi-lo)/2.
2. nums[mid] == target면 반환.
3. 왼쪽 [lo..mid]가 정렬(nums[lo] <= nums[mid])이면
   • 타겟이 [nums[lo], nums[mid]) 범위면 hi = mid - 1, 아니면 lo = mid + 1.
4. 오른쪽 [mid..hi]가 정렬(그 외의 경우)이면
   • 타겟이 (nums[mid], nums[hi]] 범위면 lo = mid + 1, 아니면 hi = mid - 1.

중복이 없으므로 좌/우 중 하나는 항상 정렬이다 → 매 반복 log n 수렴.

---

🔨 문제 풀이 과정

• 불변식: [lo..hi]는 항상 타겟 후보 구간.
• 각 반복에서 정렬된 절반을 찾고, 타겟이 들어갈 수 없는 절반을 과감히 버림.
• 구간이 비면(lo > hi) 종료.

간단 추적(예: [4,5,6,7,0,1,2], target=0)

• 초반 mid가 좌측 큰 값이면 좌측이 정렬 → 0은 좌측 범위 밖 → 우측으로 이동
• 우측 절반 정렬 구간에서 0이 들어옴 → 인덱스 4에서 히트

 

---

🔨 구현코드

package leetcode;

/**
 * 33. Search in Rotated Sorted Array
 * - 이진 탐색 + 회전 배열 처리
 * - 시간복잡도 O(log n), 공간복잡도 O(1)
 */
public class LeSolution04 {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (nums[mid] == target) return mid;

            // 왼쪽 절반이 정렬된 경우
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;   // 왼쪽으로
                } else {
                    lo = mid + 1;   // 오른쪽으로
                }
            } else { // 오른쪽 절반이 정렬된 경우
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;   // 오른쪽으로
                } else {
                    hi = mid - 1;   // 왼쪽으로
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        LeSolution04 sol = new LeSolution04();
        System.out.println(sol.search(new int[]{1,3,5,6}, 5));             // 2
        System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 0));       // 4
        System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 3));       // -1
        System.out.println(sol.search(new int[]{1}, 0));                   // -1
    }
}

---

📚 풀이 보완

코드 설명 (핵심 분기)

• nums[lo] <= nums[mid] → 좌측 정렬
  • target ∈ [nums[lo], nums[mid]) 이면 좌측으로, 아니면 우측으로
• 그 외 → 우측 정렬
  • target ∈ (nums[mid], nums[hi]] 이면 우측으로, 아니면 좌측으로

• 경계 포함/미포함 헷갈림
  • 좌측 정렬: target < nums[mid] (왼쪽 끝 nums[lo]는 포함)
  • 우측 정렬: target > nums[mid] (오른쪽 끝 nums[hi]는 포함)
• mid 재계산 망각 또는 오버플로우 가능성
  • mid = lo + (hi - lo) / 2 형태 권장

엣지 케이스

• 길이 1 배열: nums[0] == target이면 0, 아니면 -1
• 이미 정렬(비회전) 배열도 동일 로직으로 자연스럽게 처리

---

📍 Plus+

대안 접근(피벗 분리형, 2단계 이진 탐색)

1. 한 번의 이진 탐색으로 최소값 인덱스(피벗) 찾기
2. 피벗 기준으로 어느 절반에 속하는지 판단 후 일반 이진 탐색

• 중복이 없으면 현재 방식(1패스)이 더 간결

중복 허용 버전(LeetCode 81)

• 중복이 있으면 nums[lo] == nums[mid] == nums[hi] 같은 케이스에서 정렬 판별이 불가 →
  lo++, hi--로 모호성 제거 후 동일 아이디어 적용(최악 O(n) 가능)

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간 복잡도: O(log n)

• 매 반복 탐색 구간을 절반으로 축소

공간 복잡도: O(1)

• 보조 변수만 사용

• 핵심 전략: “중복 없음”을 이용해 좌/우 절반 중 하나는 정렬 → 정렬 구간에 대한 타겟 포함 판단으로 범위를 절반씩 좁힌다.
• 장점: 한 번의 이진 탐색 패턴으로 회전까지 자연스럽게 처리, O(log n)/O(1) 달성.

---

풀이 참고 로직

 

• 좌정렬 판별: nums[lo] <= nums[mid]
• 범위 체크:
  • 좌정렬: nums[lo] <= target && target < nums[mid]
  • 우정렬: nums[mid] < target && target <= nums[hi]
• 범위 밖이면 반대편으로 인덱스 이동 (lo = mid + 1 / hi = mid - 1)