[리트코드] 704. 이진 탐색 (Python)

Binary Search - LeetCode

문제

오름 차순으로 정렬된 정수 배열 nums와 정수 target이 주어질 때,  nums에서 target 값을 찾는 함수를 구현해라

과정

• 투포인터를 이용하여 배열을 탐색한다.
• 투포인터를 이용하여 중간(=mid) index를 계산한다.
• target보다 큰 수를 만난다면 end를 mid-1로 변경하고 mid를 다시 계산한다.
• target보다 작은 수를 만난다면 start를 mid+1로 변경하고 mid를 다시 계산한다.
• 이 과정에서 항상 start는 end보다 작거나 같아야 한다.

 

입력

[-1,0,3,5,9,12]

출력

9

 

풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(start, end):
            if start > end:
                return -1

            mid = (start + end) // 2

            if nums[mid] < target:
                return bs(mid + 1, end)
            elif nums[mid] > target:
                return bs(start, mid - 1)
            else:
                return mid

        return bs(0, len(nums) - 1)

 

한 줄 씩 해석해보기

def bs(start, end):
    if start > end:
        return -1

• 재귀함수를 만들어준다.
• 투포인터로 사용할 start, end값을 받는다.
• 따라서 start가 end보다 값이 커지면 -1을 return한다.

    mid = (start + end) // 2

• 투포인터를 이용하여 중간(=mid) index를 계산한다.

    if nums[mid] < target:
        return bs(mid + 1, end)
    elif nums[mid] > target:
        return bs(start, mid - 1)
    else:
        return mid

• target보다 큰 수를 만난다면 end를 mid-1로 변경하고 mid를 다시 계산한다.
• target보다 작은 수를 만난다면 start를 mid+1로 변경하고 mid를 다시 계산한다.
• 모두 아니라면 mid를 return한다.

return bs(0, len(nums) - 1)

• 초기값에는 배열의 첫 인덱스와 끝 인덱스를 넣어준다.

 

파이썬 내장 함수 풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        idx = bisect.bisect_left(nums, target)
        if idx < len(nums) and nums[idx] == target:
            return idx
        else:
            return -1

• Python에는 이진 검색 알고리즘을 지원하는 bisect모듈이 있다.

 

예외 처리 풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except ValueError:
            return -1

• try ~ except 구문으로 예외처리를 수행할 수 있다.