[LeetCode] Binary Search

69.Sqrt(x)

• 기본 while문 사용하기

class Solution(object):
    def mySqrt(self, x):
        y = 0
        
        while y*y <= x:
            y = y + 1
            
        return y-1

✅ 결과 : 1337 ms 13.3 MB

0 * 0 = 0 1 * 1 = 1 2 * 2 = 4 …

y*y가 x보다 작거나 같으면 계속 y를 증가시킨다.

8의 제곱근 : 2.8 ….. 5의 제곱근 : 2.3…..

제곱근에서 정수부분만 출력하라고 했기때문에

return y-1로 한다.

• 라이브러리 사용하기

class Solution:
    def mySqrt(self, x: int) -> int:
        return int(math.sqrt(x))

✅ 결과 : 44 ms 13.9 MB

❗️ -> 로 타입 헌팅하는 문법은 python 3.5부터 !!

• binary search 사용하기

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        
        while left <= right:
            mid = (left + right) //2
            
            if mid**2 <= x and x < (mid + 1) ** 2:
                return mid
            
            elif mid**2 > x:
                right = mid - 1
                
            else:
                left = mid + 1

✅ 결과 : 49 ms 13.8 MB

만약 x = 8이라면

0, 1, 2, 3, 4, 5, 6, 7, 8

4 이상부터는 탐색해볼 필요가 없다. 그래서 8의 중간 값(mid)을 구해준다. 정수여야해서 //로 몫만 구했다. mid = 4이다. 8의 제곱근은 2.xxx이다. 4와 9 사이의 5,6,7,8은 모두 2.xxx가 제곱근이다. 4 = 2의 제곱, 9 = 3의 제곱이다. mid의 제곱 값이 4와 9일 때 = mid가 2와 3 사이일 때의 값을 return해주면 된다..

만약 mid의 제곱이 x보다 크면 right를 mid보다 작은 값으로 옮겨줘야한다. 작다면 left를 mid보다 큰 값으로 옮겨주면 된다.

704. Binary Search

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

✅ 결과 : 247 ms 15.4 MB

나는 pivot값(중간 값)을 구할때, pivot = (left + right) // 2 이렇게 구했다.

그런데 Solution을 보니 pivot = left + (right - left) // 2 이렇게 구했다.

내 생각에는 둘 다 별 차이가 없어보였고, 도대체 무슨 차이지… 하다가

오픈카톡 방에 질문을 했는데, 호석님이 답변을 해주셨다.. 🥺

파이썬에서는 상관이 없는데, C++이나 JAVA 같은 경우, left = 15억, right = 15억 인 경우, 전자는 오버플로우, 후자는 잘 되는 현상이 있어서 저렇게 짜는 경우가 있다고 한다.

참고

https://youtu.be/eC0b6lUj84w https://leetcode.com/problems/sqrtx/discuss/1644771/sqrt-of-x-leetcode-69-python