[LeetCode] Binary Search

문제 이동

1번. 이진 검색 X - index()

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
            return -1

• 이진 검색이 아니라 그냥 해당 값의 인덱스를 찾아주는 index() 메소드 사용.

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

• target이 nums에 없으면 ValueError가 뜨기 때문에 이때는 예외처리로 -1 반환하게끔 짤 수도 있다.

2번. python 모듈 사용

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:
            print(idx)
            return idx
        else:
            return -1

• bisect.bisect_left(list, num)
  정렬된 list 중 num이 삽입될 인덱스(위치)
  같은 값이 있을 때 앞쪽(왼쪽) 위치 인덱스 반환
• bisect.bisect_right(list, num)
  위랑 똑같지만 같은 값이 있을 때 제일 마지막 (오른쪽) 위치 인덱스 반환

3번. 반복문 - 반갈반갈.. (left, right)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        result = 0
        left, right = 0, len(nums)-1

        while left <= right:
            mid = (left+right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

• 나는 처음에 리스트를 유지하고 반갈반갈이라고 생각했는데 left, right 인덱스만 사용하면 훨씬 쉽게 코드를 짤 수 있었다.
• 처음 안 사실 : mid_idx = (left_idx+right_idx)//2
  이걸 아예 처음 깨달았다. [0,1,2,3,4,5] 있을 때 left_idx=3, right_idx=5면 mid=(3+5)//2=4가 된다는 것을 이제 처음 알았다..ㅋㅋㅋ

4번. 재귀

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(left, right):
            if left <= right:
                mid = (left + right) // 2
                print(left, right, mid)

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

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

• 재귀는 -> -> -> 들어갔던거 다시 <- <- <- 이렇게 나오기 때문에 return bs()으로 해줘야 최종적으로 값이 다 빠져나오고 return 됨.
• return을 안 쓰면 깊은 곳에선 정답이 return 됐어도 처음 재귀로 돌아왔을 때 받는 게 없어서 그냥 저 마지막 return -1로 내려가 -1이 output이 된다.

속도 : bisect나 반복문이 젤 빠르다.

index()도 빠르다고 볼 수 있지만,
nums의 크기가 커지고 target이 후반부에 있을 때 index()는 매우 느려진다.
index()는 앞에서부터 차례로 찾기 때문에 최악의 경우 O(n)이 된다.
뒤에 위치한 target일수록 검색 속도가 느려진다.

반면 이진 검색은 항상 O(logn)이다.
따라서 bisect는 삽입 지점을 찾아주는 메소드지만 위치를 검색할 때도 bisect를 사용할 줄 알아야 한다.