704, Binary Search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        l, r = 0, len(nums)-1

        while l <= r:
            mid = (l+r) // 2
            if nums[mid] == target:
                return mid
            
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        
        return -1

 

풀이를 보면, 중간 값을 구하는 다른 방법을 확인할 수 있습니다.

각 방식에 대해서 ChatGPT에게 물어보면,

1. (l + r) // 2
   • 이 방법은 두 수의 합을 구한 후에 2로 나눈 후 소수점을 버립니다. (내림)
   • 이 방법은 가장 간단하지만, 중간 값이 매우 큰 경우에는 오버플로우가 발생할 수 있습니다.
2. • 이 방법은 두 수의 차를 구한 후에 2로 나눈 후 소수점을 버립니다. (내림)
   • 그 결과를 l 에 더하여 중간 값을 찾습니다.
   • 이 방법은 오버플로우의 위험이 적으며, 좀 더 안전한 방법입니다.l + {(r  - l) // 2}
3. l + r >>> 1
   • 이 방법은 두 수의 합을 구한 후 비트 연산자인 >>>를 사용하여 오른쪽으로 1 비트 이동시킵니다.
   • 이 방법은 오버플로우의 위험이 없으며, 또한 매우 효율적입니다.
   • 그러나 이해하기 어려울 수 있습니다.

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        l, r = 0, len(nums)-1

        while l <= r:
            mid = l + ((r-l)//2)
            if nums[mid] == target:
                return mid
            
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        
        return -1

• 두 번째 방법으로 다시 풀어보면, 테스트 예제의 차이가 있어서 그런지 큰 차이를 보이지는 않습니다.