BST: 153. Find Minimum in Rotated Sorted Array ★

153. Find Minimum in Rotated Sorted Array

 

class Solution:
    def findMin(self, nums: List[int]) -> int:
        """
        회전된 정렬 배열에서 최소값을 찾는 함수.
        배열은 오름차순으로 정렬된 상태에서 몇 번 회전된 상태일 수 있다.
        예: [4, 5, 6, 7, 0, 1, 2]

        Find the minimum value in a rotated sorted array.
        The array was originally sorted in ascending order but may have been rotated.
        Example: [4, 5, 6, 7, 0, 1, 2]

        피벗(Pivot):
        - 배열이 정렬된 상태에서 회전되면서 정렬이 깨진 지점을 의미.
        - 피벗은 배열의 최소값이 위치한 곳이다.
        - 예: [4, 5, 6, 7, 0, 1, 2]에서 피벗은 0의 위치(인덱스 4).
        ---
        Pivot:
        - The point in the array where the sorted order is broken due to rotation.
        - The pivot is the location of the minimum value in the array.
        - Example: In [4, 5, 6, 7, 0, 1, 2], the pivot is 0 at index 4.
        """
        
        # 변수 초기화 (Initialize pointers)
        l, r = 0, len(nums) - 1  # 배열의 왼쪽(l)과 오른쪽(r) 포인터 설정
                                 # Set pointers to the left (l) and right (r) ends of the array.

        while l <= r:
            mid = (l + r) // 2  # 중간 인덱스 계산 (Calculate the middle index)
            
            # mid가 피벗 위치인지 확인
            # Check if the mid is the pivot
            # mid가 최소값이라면, nums[mid-1] > nums[mid] 조건을 만족
            # If nums[mid-1] > nums[mid], nums[mid] is the smallest value (pivot)
            if 0 <= mid - 1 and nums[mid - 1] > nums[mid]:
                return nums[mid]  # nums[mid]가 최소값이므로 반환 (Return the minimum value)

            # nums[0] <= nums[mid]인 경우:
            # - nums[0]은 배열의 첫 번째 값.
            # - nums[0] <= nums[mid]는 mid를 포함한 왼쪽 부분이 정렬된 상태임을 의미.
            # - 이 경우 최소값은 오른쪽에 위치하므로 검색 범위를 오른쪽으로 좁힘.
            # 
            # If nums[0] <= nums[mid]:
            # - nums[0] is the first element of the array.
            # - nums[0] <= nums[mid] means the left side, including mid, is sorted.
            # - In this case, the minimum value must be on the right, so shift the search range to the right.
            #
            # "="가 포함된 이유:
            # - 배열이 회전되지 않은 경우(예: [1, 2, 3, 4, 5])에는 nums[0] == nums[mid]일 수 있음.
            # - 이 경우도 오른쪽으로 이동해야 함.
            # 
            # Why include "=":
            # - If the array is not rotated (e.g., [1, 2, 3, 4, 5]), nums[0] == nums[mid].
            # - Even in this case, we should move to the right.
            if nums[0] <= nums[mid]:
                l = mid + 1  # 검색 범위를 오른쪽으로 이동 (Shift the search range to the right)
            else:
                r = mid - 1  # 그렇지 않다면, 검색 범위를 왼쪽으로 이동 (Otherwise, shift to the left)

        # while문이 종료되었지만 피벗을 찾지 못한 경우
        # 배열 전체가 정렬된 상태이므로 첫 번째 값이 최소값
        # If the while loop ends without finding the pivot,
        # the array must be fully sorted, and the first element is the minimum value.
        return nums[0]

 

아래가 맞는 거라는데, .. 둘다 통과는 함

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # 이진 탐색을 사용하여 최소값(피벗)을 찾습니다.
        l, r = 0, len(nums) - 1

        while l < r:  # 종료 조건은 l == r
            mid = (l + r) // 2

            # 오른쪽 구간에 피벗이 있는 경우
            if nums[mid] > nums[r]:
                l = mid + 1
            else:  # 왼쪽 구간에 피벗이 있는 경우
                r = mid

        # l == r이 되면 최소값이므로 반환
        return nums[l]

 

이걸로 숙지하자!!

 

class Solution:
    def findMin(self, nums: List[int]) -> int:
        
        # find pivot: pivot index를 mid로.. mid 가 최소값

        def find_pivot_index():
            l, r = 0, len(nums)-1

            while l<=r:
                mid = (l+r)//2

                if 0<= mid-1 and nums[mid-1] > nums[mid]: # mid: pivot index
                    return mid
                
                if nums[0] <= nums[mid]: # 왼쪽은 정렬이 된거니, 오른쪽을 찾아야 함
                    l = mid +1
                else:
                    r = mid -1

            # 못찾으면, 정렬된 행렬임
            return 0


        idx = find_pivot_index()
        return nums[idx]