leetcode 33(이분 탐색), 81(이분 탐색), 153(이분 탐색)

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

[4,5,6,7,0,1,2] 처럼 sorted된 리스트가 두개가 있다고 생각한다. 그리고 그중에 target을 log(n)의 시간복잡도로 찾아야 한다. log(n) 보자마자 이분 탐색을 떠올려야 하고, 그러면 저렇게 반이 섞여진곳에서 어떻게 이분탐색을 할까? 생각해보자.

난 먼저 값이 변하기 시작하는 부분의 인덱스를 찾았다. (위의 [4,5,6,7,0,1,2]의 경우엔 4) 그리고 target이 변하기 시작하는 부분 전의 안에 있는지 후에 있는지 검사후 low와 high를 정한다. [4,5,6,7,0,1,2]의 경우엔 [4,5,6,7]과 [0,1,2]로 나눠질수 있는데 각각의 리스트들을 정렬되었으므로 첫번째 값과 마지막 값 사이에 target이 들어갈지만 확인하면 된다.

low와 high를 잘 정했으면 한번더 이분탐색을 해준다.

class Solution(object):
    def search(self, nums, target):
        if not nums:
            return -1

        l, h = 0, len(nums) - 1
        while l != h:
            m = (l + h) / 2
            if nums[m] < nums[h]:
                h = m
            else:
                l = m + 1
        m = l  # 변하기 시작하는 인덱스가 여기임.

        l, h = 0, m - 1 if m > 0 else 0  # low high는 0 ~ m-1로 했다가..
        if not (nums[l] <= target <= nums[h]):  # 이 범위 안에 없으면 m ~ len(nums)-1로 해줌.
            l, h = m, len(nums) - 1

        m = -1
        while l != h:
            m = (l + h) / 2
            if nums[m] == target:
                return m
            if nums[m] < target:
                l = m + 1
            else:
                h = m

        return l if nums[l] == target else -1

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

이번엔 위의 33번과 똑같은데 중복이 될수도 있다고 한다. 중복이 나타나면서 주의해야 할 부분은 값이 변하기 시작하는 부분의 인덱스를 찾는 로직을 조금 더 세분화해야한다는것이다.

class Solution(object):
    def search(self, nums, target):
        if not nums:
            return False

        l, h = 0, len(nums) - 1
        while l != h:  # 이 안의 로직만 변경.
            m = (l + h) / 2
            if nums[m] < nums[h]:
                h = m
            elif nums[h] == nums[h-1]:  # 같은 값이 h에서 반복되고있으면 h -= 1
                h -= 1
            elif nums[l] == nums[l+1]:  # 같은 값이 l에서 반복되고있으면 l += 1
                l += 1
            else:
                l = m + 1

        m = l
        l, h = 0, m - 1 if m > 0 else 0
        if not (nums[l] <= target <= nums[h]):
            l, h = m, len(nums) - 1

        m = -1
        while l != h:
            m = (l + h) / 2
            if nums[m] == target:
                return True
            if nums[m] < target:
                l = m + 1
            else:
                h = m

        return True if nums[l] == target else False

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

위 33번의 코드를 가져온다. 그리고 변하기 시작하는 인덱스를 구하고 최소값은 

min(nums[0], nums[변하기 시작하는부분의 인덱스]) 이다. 

class Solution(object):
    def findMin(self, nums):
        if not nums:
            return -1
 
        l, h = 0, len(nums) - 1
        while l != h:
            m = (l + h) / 2
            if nums[m] < nums[h]:
                h = m
            else:
                l = m + 1
        m = l  # 변하기 시작하는 인덱스가 여기임.
 
        return min(nums[0], nums[m])