[이진탐색] Leet code 704. Binary Search

리트코드 704번
정렬된 배열에서 target값을 찾아 index값을 반환

풀이1 재귀

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        def BS(left, right):
            if left > right:
                return -1

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

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

• python에서 재귀 호출 최대수는 1000번으로 재귀알고리즘을 짤 때 넘지 않도록 참고
  
  

풀이2 반복문

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

        return -1

Binary Search 알고리즘의 버그

binary search 알고리즘에서 중간값(Mid)를 구하는 식을 (left + right) // 2로 작성하기도한다. 이는 양끝 인덱스의 평균값을 구하는 것으로 아주 직관적이고 익숙하다
하지만 자료형에는 최댓값이 정해져있으므로 int의 최대값을 left + right에서 넘어버린다면 오류가 발생할 것이다

따라서 해결책은 left + (right - lef) // 2 이다. 즉 left에서 둘 간격의 반 만큼 더 더해주는 방식을 택해서 overflow문제를 해결하는 것이다.

오랫동안 아무도 발견하지 못한 버그일만하다...ㅎㅎ