[LeetCode] 704. Binary Search

문제링크

https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

 

코드

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 target==nums[pivot]:
                return pivot
            elif target<nums[pivot]:
                right = pivot-1
            else:
                left = pivot+1
        return -1

 

POINT

- 풀이방법

Binary Search문제이다.

탐색할 범위를 지정하고 그 가운데를 pivot으로 지정한다.
pivot이 가리키는 값과 target을 비교해서 

pivot값이 더 크다면 범위를 (left~pivot-1)로 재정의하고,
pivot값이 더 작다면 탐색 범위를 (pivot+1~right)로 정의한다.  

 

- Complexity Analysis

마스터 정리를 사용하여 시간복잡도를 계산할 수 있다.

1) Time Complexity : O(logN)

마스터 정리를 적용하면, a=1이고 b =2
--> T(N) = 1*T(N/2) + Θ(1) 

 

2) Space Complexity : O(1) (b/c constant space)

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=yyj9301&logNo=221240585554 

마스터 정리 Master Theorem 알고리즘 시간 복잡도 구하기