Binary Search

Binary Search - LeetCode

접근 방법 [필수 작성]

제한 조건 확인

• 리스트 길이가 최대 10^4 이므로 완전탐색해도 무리가 없음
• 모든 원소값은 고유한 값이고 오름차순 정렬이기 때문에 바로 이진탐색을 적용할 수 있음

3가지 방법으로 구현 연습

• 반복문
• 재귀
• bisect 라이브러리 활용

코드 구현 [필수 작성]

3가지 방법으로 구현 연습

• 반복문

#12시 25분 시작 -> 12시40분 끝
#3가지 방법으로 구현 (반복문, 재귀, bisect 라이브러리 활용)

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

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

• 재귀

#12시 25분 시작 -> 12시40분 끝
#3가지 방법으로 구현 (반복문, 재귀, bisect 라이브러리 활용)

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

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

• bisect 라이브러리 활용

#12시 25분 시작 -> 12시40분 끝
#3가지 방법으로 구현 (반복문, 재귀, bisect 라이브러리 활용)
import bisect
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums,target)
        if index != len(nums) and nums[index] == target:
            return index
        return -1

배우게 된 점 [ 필수 X ]

자유 형식

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!