[1스4코2파] # 191. LeetCode 153. Find Minimum in Rotated Sorted Array

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (191차)
[4코1파] 2023.01.13~ (183일차)
[1스4코1파] 2023.04.12~ (94일차)
[1스4코2파] 2023.05.03 ~ (72일차)

Today :

2023.07.13 [191일차]
binary_search
153. Find Minimum in Rotated Sorted Array

153. Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

문제 설명

unique한 숫자의 오름차순 원소로 구성되어 회전된 배열이 주어졌을 때,
해당 array에서 가장 작은 원소를 찾음

문제 풀이 방법

binary search로 푼다.
조건을 적절히 줘서 가장 작은 원소를 log(n) 시간복잡도로 찾아야 한다.
left, right를 0과 배열의 길이 만큼 준다음에
왼쪽 포인터와 오른쪽 포인터의 배열의 원소를 확인하고 최소값을 찾고,
binary search로 최소값을 찾아가낙ㅁ

내 코드

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

        while left <=right:
            if nums[left] <= nums[right]:
                ans = min(ans, nums[left])
                break

            mid = (left + right) //2
            ans = min(ans, nums[mid])

            if nums[mid] >= nums[left]:
                left = mid + 1
            else:
                right = mid -1

        return ans

증빙

여담

에흉 별 문제가 다있네