Leetcode 33. Search in Rotated Sorted Array(Binary Search)

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

Search in Rotated Sorted Array - LeetCode

 

---

 

얼핏보면 간단한 문제 같지만 O(logn)이라는 조건이 붙어있는만큼, Binary Tree 로 풀어야 하는 문제였습니다

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return nums.index(target) if target in nums else -1

저처럼 이렇게 풀면 안되는,,,,

 

얼마전에 Binary Search Tree를 공부했기 때문에 그래도 코드를 이해하면서 따라갈 수 있었는데요

 

2022.09.26 - [분류 전체보기] - Binary Tree & Binary Search Tree

Binary Tree & Binary Search Tree

 

---

 

Binary Search Tree의 원리를 활용한 풀이를 살펴보겠습니다!

 

class Solution:
    def search(self, A: List[int], target: int) -> int:
        n = len(A)
        left, right = 0, n - 1
        if n == 0: return -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if A[mid] == target: return mid
            
            if A[mid] >= A[left]:
                if A[left] <= target < A[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
                    
            else:
                if A[mid] < target <= A[right]:
                    left = mid + 1
                else:
                    right = mid - 1

 

우선 Binary search Tree의 주목적이 뭘지 생각해보면 일일이 다 찾는게 아니라 왼쪽 자식 노드는 root 보다 작은 값,

오른쪽은 더 큰 값이 있는 구조상의 특성을 활용해서 더 빨리 값을 찾자는데에 목적이 있습니다.

 

이 문제에서는 A[mid] >= A[left] 왼쪽으로 rotate했을 때 만약에 값이 중간값 기준 왼쪽에 있으면 left rotation을 \

실행했다는거겠죠. 만약 값이 시작점에서 중간값 사이에 있다면 mid보다 큰 값은 볼 필요가 없어지기 때문에 mid-1을 해주고 그렇지 않다면 반대쪽에 있는 것이기 때문에 mid+1을 해주겠죠

 

똑같은 논리를 바탕으로 right rotation한 상황을 생각해보고 점차 값을 좁혀 나가면 A[mid] == target이 되는 값을 찾을 수 있게 됩니다