[LeetCode 해석 및 풀이] 704. Binary Search

LeetCode 문제 해석 및 풀이 방법

 

문제 704. Binary Search(이진 탐색)

바로가기

 

문제 설명

영문

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

 

한글

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어지면, nums에서 target을 찾는 함수를 작성하시오. 타겟이 존재한다면 index를 반환하고 아니면 -1을 반환하세요.

 

반드시 O(logn)의 시간복잡도로 작성하여야 합니다.

 

제한조건

• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

 

입출력 예

입력	출력
nums = [-1,0,3,5,9,12], target = 9	4
nums = [-1,0,3,5,9,12], target = 2	-1

 

 

해답 및 해설

파이썬 (Python)

반복문을 이용한 해답

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

        while left <= right:
            mid = (right+left)//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:
        if not nums: return -1

        mid = (len(nums)-1) // 2

        if nums[mid] < target:
            result = self.search(nums[mid+1:], target)
            if result != -1 :
                result += mid+1
        elif nums[mid] > target:
            result = self.search(nums[:mid], target)
        else:
            result = mid

        return result

와! 재귀!

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            if left > right: return -1

            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
        
        return binary_search(0, len(nums)-1)

반복문을 이용한 것과 비슷한 이런 느낌도 가능함