[LeetCode] 33. Search in Rotated Sorted Array.

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

Search in Rotated Sorted Array - LeetCode

 

이분탐색을 활용한 문제. 

보통 (lo + hi) // 2로 mid값을 갱신해주는데, lo + (hi - lo) // 2라는 코드를 발견했다. 찾아보니 오버플로우를 방지하기 위한 연산이다. 예를 들어 lo = 3, hi = 2,147,483,647 라고 생각해보자. (3 + 2,147,483,647) // 2 를 연산하면 hi는 int 값의 범위의 max에 해당하기 때문에 오버플로우가 발생한다. 즉, 3 + 2,147,483,647 = -3이 되어 최종적인 계산에서는 -3 // 2 가 수행된다. 이를 방지하기 위해 lo + (hi - lo) // 2를 사용한다. 계산하게 되면 3 + (2,147,483,647 - 3) // 2 = 1,023,.... 어쩌구저쩌구가 나온다. 오늘도 하나 배웠다 !

class Solution:
    def search(self, nums, target):
        if not nums:
            return -1
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low) // 2
            if target == nums[mid]:
                return mid

            # mid가 nums[low]보다 큰 경우에는 오름차순 정렬이 되어있다. 
            # 즉, 어떤 pivot을 기준으로 rotate가 되지 않은 상태임을 뜻한다. 
            
            if nums[low] <= nums[mid]: # low ~ mid는 정렬되어 있는 상태 

                # target이 범위 내에 존재한다면 high범위를 mid - 1로 조절한다.
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1
                # 그렇지 않다면 low값을 조절한다. 
                else:
                    low = mid + 1

            # nums[mid]가 low보다 작다면 해당 값은 어떤 pivot에 의해 
            # rotate가 된 배열의 값 중 하나임을 뜻한다.

            else: # mid ~ high가 정렬되어 있는 상태 
                if nums[mid] <= target <= nums[high]: 
                    low = mid + 1
                else:
                    high = mid - 1

        return -1