[1스4코2파] # 192. LeetCode 33. Search 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~ (192차)
[4코1파] 2023.01.13~ (184일차)
[1스4코1파] 2023.04.12~ (95일차)
[1스4코2파] 2023.05.03 ~ (73일차)

Today :

2023.07.14 [192일차]
binary_search
33. Search in Rotated Sorted Array

33. Search in Rotated Sorted Array

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

문제 설명

오름차순으로 정렬된 정수 배열 nums이 회전되어 output 배열이
배열이 [nums[k], nums[k+1], ... , nums[n-1], nums[0], nums[1], ..., nums[k-1]] (인덱스 0) 됐는데,
예를 들면 [0,1,2,4,5,6,7]은 피벗 인덱스 3에서 회전하여 [4,5,6,7,0,1,2]가 된 것.

회전 후의 대상의 인덱스가 해당 배열의 원소에 해당하면, 대상의 인덱스를 반환하고 아니면 -1을 반환함.
O(log n) 시간 복잡도로 풀어야 함

문제 풀이 방법

binary search로 푼다.
조건을 적절히 줘서 가장 작은 원소를 log(n) 시간복잡도로 찾아야 한다.
조건이 까다로움 neetcode 보고 풀었음
아 이해안돼 머리가 이해하기 싫은 모양임
어쩌겠냐 하지말아라

내 코드

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

증빙

여담

한번에 풀리면 얼마나 좋냐 릿코드야 너도 좋고 나도 좋고
왜 서로 번거롭게 까다로운 문제가 나오고 난리
제로섬 게임