[leetCode #704] Binary Search

 

Q. 정렬된 배열 num와 찾아야하는 target이 주어집니다.

nums 배열에서 target을 찾을 수 있다면 nums의 어디에 있는지 index를 반환해주세요.

이 문제는 O(log n) 시간복잡도를 갖는 알고리즘을 사용하여 풀어야합니다.

 

 

 

 

A.

이 문제는 시간복잡도가 O(log n)을 갖는 알고리즘으로 풀어야합니다. 일반적인 순차탐색은 O(n)이기에 다른 방법을 사용해야합니다.

필요한 알고리즘은 이진탐색입니다. 이진탐색을 정렬된 배열을 반으로 쪼개가며 target을 찾는 방식이여서 시간복잡도가 O(log n)입니다.

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(start,end):
            if start > end:
                return -1
            mid = (start+end) // 2

            if nums[mid] < target:
                return bs(mid+1, end)

            if nums[mid] > target:
                return bs(start, mid -1)
            
            else:
                return mid
        
        return bs(0, len(nums)-1)

 

필요한 것을 정리해보겠습니다.

1. nums 배열의 중간값을 찾는다.

2-1. nums의 첫번째요소 부터 중간값 이전요소 안에 target이 있다면?

2-2. nums의 중간값 이후요소 부터 마지막요소 안에 target이 있다면?

2-3. nums의 중간값이 찾고있는 target이라면?

 

해당 정답코드는 이 조건들을 재귀적으로 반복하며 2-3을 만족할때까지 진행됩니다.

 

결국 찾는값이 있다면 else문에 걸리게 되고 해당 인덱스인 mid를 반환하게 됩니다.

 

만약 찾는값이 없다면?

 

이 로직에서 찾는 값이 없다면 start값이 end보다 커지게 만들어져 있습니다. 때문에 -1을 반환하게 됩니다. 

 

예시코드로 찾는 값이 nums배열에 없을 때, start와 end의 값을 확인해보겠습니다.

 

 

재귀함수로 돌고 돌며, start와 end값을 찍어냅니다. 찾는 tartget값이 없으니 (start가 end보다 커졌으니) -1을 반환하는 것입니다.

 

문제 해결쓰!