[알고리즘/python] LeetCode 153. Find Minimum in Rotated Sorted Array - 이진 검색 풀이

📑 1. 문제 이해

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150 

Find Minimum in Rotated Sorted Array - LeetCode

이 문제는 오름차순 정렬된 테이블을 오른쪽으로 회전시킨 배열에서 최소 원소를 찾는 문제입니다.

- 배열은 중복된 원소를 포함하지 않습니다.

- O(LogN) 복잡도를 가지는 알고리즘을 구현해야합니다.

- 배열의 길이가 최소 1입니다.

- 원소는 음수가 될 수 있습니다.

☑️ 테스트케이스

문제에서 주어진 테스트 케이스를 살펴보면 다음과 같습니다. 

 

1) Example1: nums = [3, 4, 5, 1, 2]

    - 오른쪽으로 3번 회전된 배열입니다. 

 

2) Example2: nums = [4,5,6,7,0,1,2]

    - 오른쪽으로 4번 회전된 배열입니다. 

 

3) Example3: nums = [11,13,15,17]

    - 오른쪽으로 4번(배열의 길이) 회전된 배열입니다. 배열의 길이만큼 회전시킨 결과는 원래 배열과 같습니다.

 

더 살펴볼 테스트 케이스는 다음과 같습니다.

 

4) nums = [1]

    - 배열의 길이가 1입니다.

 

5) nums = [2,3,1] 

    - 가장 작은 원소가 배열의 끝에 위치합니다. 

 

💡 2. 알고리즘 설계

 최소값을 찾기 위해서는 이전 원소보다 값이 작아지는 인덱스를 찾으면 됩니다. 오름차순 정렬된 배열에서는 최솟값을 제외하고는 이전 원소보다 항상 크기 때문입니다. 이때, 선형 탐색을 통해 최솟값 인덱스를 찾는다면 O(N) 시간 복잡도를 가지게 되어 문제의 조건을 만족하지 못합니다.

 

 정렬된 배열에서 특정 원소를 빠르게 검색하기 위해 이진 검색을 활용할 수 있습니다. 특정 값을 target으로 이진 검색을 수행할 수도 있지만 특정 조건을 target으로 이진 검색을 수행할 수 있습니다. 여기서는 조건이 arr[i] < arr[i-1]이 됩니다.

 

 mid가 조건을 만족하지 않는 경우 mid를 기준으로 왼쪽 혹은 오른쪽을 탐색해야합니다. 어떤 방향을 선택할 것인지를 결정하기 위해  배열의 마지막 원소와 비교할 수 있습니다. 현재 원소가 배열의 마지막 원소보다 작다면 최소값을 찾기 위해 더 작은 원소들을 탐색해야 하므로 왼쪽 방향을 선택합니다. 현재 원소가 배열의 마지막 원소보다 크다면 회전된 배열이며, 최소값을 찾기 위해 더 큰 원소들을 탐색해야 합니다. 왜냐하면 최솟값은 가장 큰 원소보다 오른쪽에 위치하기 때문입니다.

 

1. 배열의 길이가 1이라면 배열의 유일한 원소를 반환합니다.

2. 이진 탐색의 범위를 한정하는 두 포인터 lo, hi를 초기화합니다.

3. 가운데값 mid를 기준으로 조건(이전 원소보다 작은 값인지) 을 만족하는지 확인합니다. 조건을 만족한다면 그 원소를 반환합니다.

4. 조건을 만족하지 않는다면 이진 탐색할 범위를 조정합니다. arr[mid]가 배열의 마지막 값보다 더 크다면 오른쪽을 탐색하고, 배열의 마지막 값보다 더 작다면 왼쪽을 탐색합니다.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        lo = 0
        hi = len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] < nums[mid - 1]:
                return nums[mid]
            if nums[mid] < nums[-1]:
                hi = mid - 1
            else:
                lo = mid + 1

시간 복잡도 및 공간 복잡도

시간 복잡도: O(LogN). 이진 탐색은 범위를 반으로 줄여가며 탐색하므로 O(LogN) 복잡도를 가집니다.

공간 복잡도: 주어진 배열을 탐색하는 것으로 변수를 제외한 별도의 배열이 필요하지 않습니다.

 ⎌ 4. 검토

테스트 케이스들을 검토해보면 다음과 같습니다.

 

1) Example1: nums = [3, 4, 5, 1, 2]

    - 이전 원소보다 값이 작아지는 인덱스 3을 찾을때까지 2번 탐색합니다.

 

2) Example2: nums = [4,5,6,7,0,1,2]

    -   이전 원소보다 값이 작아지는 인덱스 4을 찾을때까지 3번 탐색합니다.

 

3) Example3: nums = [11,13,15,17]

    - 이진 검색으로 모든 원소를 검사하기 때문에 최소 원소가 배열의 처음에 위치하여도 찾을 수 있습니다. 총 2번 탐색합니다.

 

4) nums = [1]

    - 반복문을 수행하기 전에 함수가 종료됩니다.

 

5) nums = [2,3,1] 

    - 이진 검색으로 모든 원소를 검사하기 때문에 최소 원소가 배열의 끝에 위치하여도 찾을 수 있습니다.

---

✅ 정리

◎ 이진 검색은 특정 값을 타겟으로 원소를 검색할때 뿐만 아니라, 특정 조건을 만족하는 원소를 타겟으로 검색할때도 사용됩니다.