[리트코드] 704. Binary Search

# 문제 설명

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

만약 target 값이 존재한다면, 그 index를 반환한다. 그렇지 않으면 -1 을 반환한다.

실행시간 복잡도는 O(log n) 의 알고리즘 이어야 한다.

 

# 입출력 예시

입력	출력
nums = [-1,0,3,5,9,12] target = 9	4
nums = [-1,0,3,5,9,12] target = 2	-1

 

# 코드 풀이 1.  재귀 풀이

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

 

# 코드 풀이 2.  반복문 풀이

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

 

# 코드 풀이 3.  예외처리 풀이

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

 

 

# 핵심 포인트

• Python 에는 이진 검색 알고리즘을 지원하는 bisect 모듈이 있다. 이를 사용하여 풀 수도 있다.
• try ~ except 구문으로 예외처리를 수행할 수 있다.