[이진 검색] 이진 검색

704 | Binary Search
https://leetcode.com/problems/binary-search/

 

 

 

이상 풀이

 

재귀 풀이

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            if left <= right:
                mid = (left + right) // 2

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

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

 

• 정렬된 nums 를 입력받기 때문에 따로 정렬이 필요 없음
• index 값을 return 하기 때문에 mid return

 

 

반복 풀이

 

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

            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

 

• 재귀 풀이는 우아한 편, 반복 풀이는 좀 더 직관적 -> 이해하기 쉬움

 

 

이진 검색 모듈

 

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
        else:
            return -1

 

• 이진 검색 알고리즘 지원 - bisect 모듈 

 

 

이진 검색을 사용하지 않는 index 풀이

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except ValueError:
            return -1

 

• index -> 존재하지 않는 값이면 에러 발생, 에러 처리해줌
• 이진 검색 X