[리트코드] Binary Search(python)

LeetCode, Binary Search(이진 탐색/검색)

TL;DR

• 이진 탐색(Binary Search)

문제 요약

1. 오름차순으로 정렬된 유일한 원소를 갖고 있는 정수 배열 nums와 정수 target이 주어진다.
2. 주어진 nums와 target에 대해서 target이 nums에 존재하는지 찾는 함수를 작성하라.
3. 만약 target이 존재한다면 해당 인덱스를 반환하고, 존재하지 않는 경우에는 -1을 반환한다.
4. 시간 복잡도는 반드시 O(logn)이 되어야 한다.

 

- 오름차순으로 정렬된 배열과 찾아야 하는 정수, O(logn)의 시간복잡도를 통해 Binary search를 통해 문제를 해결해야 함을 알 수 있다.

  (정렬된 배열, O(logn)의 시간복잡도는 Binary search의 대표 특징들이다.)

입출력 형태

입출력 예시

풀이

Binary search를 구현하는 방법은 여러 가지가 존재한다.

첫 번째 방법은 재귀적으로 해결하는 방법이다. 중간 지점을 찾기 위한 left와 right를 매개 변수로 갖는 재귀 함수를 작성한다.

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

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

 

- 중간 지점의 인덱스(mid)일 때의 값이 target과 일치한다면 해당 값을 반환한다.

- mid일 때의 값이 target보다 작을 경우 target은 mid 이후의 인덱스에 존재할 것이기 때문에 left를 mid + 1로 하여 재귀 함수를 실행한다.

- mid일 때의 값이 target보다 클 경우 target은 mid 이전의 인덱스에 존재할 것이기 때문에 right를 mid - 1로 하여 재귀 함수를 실행한다.

- 찾는 값이 존재하지 않는 경우(left > right)에는 -1을 반환한다.

 

두 번째 방법은 반복문으로 해결하는 방법이다. 구현한 로직은 재귀일 때와 동일하다.

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

 

세 번째 방법은 `bisect` 모듈을 사용하는 방법이다. python에는 Binary search를 구현해 둔 bisect 모듈이 존재한다. 이를 사용해서 문제를 해결할 수 있다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        import bisect
        
        # 정렬 순서를 유지하도록 target이 들어갈 index를 반환
        index = bisect.bisect_left(nums, target)

        if index < len(nums) and nums[index] == target:
            return index
        else:
            return -1

 

bisect 모듈의 `bisect_left` 메소드는 주어진 nums에서 정렬된 순서를 유지하며 target이 들어갈 수 있는 index를 반환하는 함수이다.

즉, target을 삽입하기 좋을 때의 index가 target의 값이라면, 이미 리스트에는 target이 존재한 것이므로 해당 index를 반환하면 된다. 이 때, index의 값이 리스트의 길이를 넘어서면 안된다. 해당하는 경우는 배열에 target이 없는 경우이다.

그렇지 않은 경우는 주어진 리스트에 target이 존재하지 않는 경우이므로 -1을 반환한다.