[파이썬(python) 알고리즘] 이진 탐색(Binary Search)

이진 탐색 (Binary Search)

  이진탐색은 배열의 중앙값(median)을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 대략 반으로 줄여가며 재귀적으로 진행하는 알고리즘이다(물론 반복으로도 구현 가능하다). 정렬된 배열에서의 탐색에 적합한 알고리즘이다(연결리스트에서는 부적합함. 가운데 지점을 빠르게 찾을 수 없기 때문이다). 

  시간복잡도는 $O(\log_2{n})$ 으로 빠른 수행시간을 보여준다. 

34를 이진 탐색하는 경우

 

이진 탐색 알고리즘

1) 재귀 구현

 

2) 반복 구현

 투 포인터를 어떻게 활용하느냐의 차이로 투 포인터의 응용이라고 볼 수도 있을 듯하다.

 

이진 탐색 in Python

  bisect 모듈에 구현이 되어 있으며, bisect_left를 사용하면 된다. 원래는 정렬된 리스트를 삽입 후에 다시 정렬할 필요가 없도록 기능하는 모듈이므로, 탐색 실패 시에 리턴하는 값이 해당 item이 정렬된 리스트 내에서 삽입될 위치(기존 항목의 왼쪽 → "left"인 이유)를 리턴한다. 따라서 해당 모듈을 사용할 때에 탐색 실패 시 예외처리를 별도로 더 해줄 필요가 있다. 실제 탐색할 아이템이 배열 내의 최댓값보다 큰 경우에는 배열 길이를 리턴하기 때문에 index out of range error가 발생할 가능성이 있다. 또한 lo, hi 인자도 있는데 이는 시작점과 끝점을 지정하기 때문에 배열의 범위를 좁혀가며 반복적으로 이진탐색을 실시할 때 등에 유리하게 사용될 수 있다.

def search(self, nums: List[int], target: int) -> int:
    index = bisect.bisect_left(nums, target) # bisect 모듈 사용하여 이진 검색
    print(index) 
    if index < len(nums) and nums[index] == target:
        return index
    else:
        return -1

 

 한편 파이썬에서는 list의 index 메소드를 이용하면 탐색하고자 하는 아이템의 인덱스를 빠르게 얻을 수 있다. 그러나, index메소드는 왼쪽부터 차례대로 탐색을 진행하므로 탐색하고자 하는 아이템이 배열의 오른쪽에 위치해있다면 $O(n)$으로 비효율적이다. 이 경우에는 이진 탐색이 index 메소드보다 훨씬 효율적일 수 있다.