leet code 33 - Search in Rotated Sorted Array

문제 자체의 난점은 log 시간 안에 풀수 있느냐에 있다.

 

정렬된 리스트, log의 시간, 중복 없는 고유 리스트. 이진탐색 응용으로 풀 수 있는 문제이다.

 

문제의 해설을 잘 읽어보면 연속적인 리스트의 최우단을 최 좌단으로 순환 시킨다. 즉 pivot. 이산되는 구간이 발생한다.

 

그리고 이산되는 구간에서는 오름차순의 배열 두개가 생기는 것과 마찬가지이다.

 

그리고 항상 왼쪽의 배열이 오른쪽의 배열보다 크다.

 

알다시피 이진 탐색의 포인터는 세개. l, m, r이다.

 

먼저 tartget 값이 m과 같다고 해보자. 그러면 그대로 인덱스를 반환하면 된다.

 

만약 m이 왼쪽의 이산되는 구간에 있다고 해보자.

그리고 target 값이 m 보다 크다고 해보자.

 

이미 m의 왼쪽에서는 target 값이 없다는 것을 알 고 있다.그렇다면 우리가 탐색해야 할 부분은 m에서 오른쪽에 있는 부분들이다.

 

만약 m이 왼쪽의 이산되는 구간에 있고,

target 값이 m보다 작다고 생각해보자.

 

그렇다면 우리가 탐색해야 할부분은 m에서 왼쪽에 있는 부분들과, 

다시 오른쪽의 일부가 된다. 하지만 바이너리 서치에서 이런 접근은 옳지 않다. 왼쪽과 오른쪽을 동시에 탐색할 수 없기 때문이다. 

하지만 최 좌단값과 target 값을 비교해서 최좌단값보다도 작다면, mid의 왼쪽이 아니라 오른쪽에 있다는 것을 알 수 있다.

 

하지만 최좌단값과 target을 비교해 최 좌단값보다 크거나 같다면 mid의 왼쪽을 탐색해야한다.

 

이제 다시 m이 오른쪽의 이산되는 구간에 있다고 해보자. 

그리고 target 값이 m보다 작다고 해보자. 그렇다면 우리는 mid의 왼쪽에 대해 탐색해야하는걸 알 수 있다.

 

m이 오른쪽의 이산되는 구간에 있고 , target은 m보다 크다고 해보자. 그럼 다시 오른쪽 왼쪽이 전부 탐색해야하는 구간에 속하게 된다. 

이때는 전에서 최좌단값을 썼던 것 처럼 최 우단 값을 쓸 수 있다. 

 

이상황에서 target이 최우단값보다 크다면. 어떨까? 그렇다면 왼쪽에 대해 탐색해야 함을 알 수 있다.

 

만약 최우단값보다 작거나 같다면 어떨까? 그렇다면 오른쪽에 대해 탐색해야 할 것이다. 

 

이러면 모든 조건 분기에 대한 판단이 끝났다.

 

그런데 가장 근본적으로, m이 왼쪽의 이산되는 구간에 있는지, 오른쪽의 이산되는 구간에 있는지는 어떻게 판단할 것인가? 

m이 l보다 크다면, 오름차순. 즉 왼쪽의 구간에 있다는 것을 의미한다. 

만약 m이 l보다 작거나 같다면 오른 쪽의 구간에 있다는 것을 의미한다. 

 

---

이진 탐색 응용풀이

 

 

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        #리스트에서 target을 찾고 target의 원래 nums에서의인덱스를 반환한다.
        #만약에 target이 없다면 -1반환. 

        l, r = 0, len(nums)-1

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

            if nums[m] == target:
                return m

            if nums[m] >= nums[l]:
                if target > nums[m]:
                    l = m + 1
                elif target < nums[l]:
                    l = m + 1
                else:
                    r = m -1

            else:
                if target < nums[m]:
                    r = m -1
                elif target > nums[r]:
                    r = m - 1
                else:
                    l = m + 1

        return -1