[Python] 이진탐색(Binary Search)

1. 이진탐색?

- 이진탐색은 정렬되어 있는 선형자료구조에서 사용할 수 있는 탐색 방법이다.

- 정렬되지 않은 자료형의 경우 처음부터 차례대로 값을 비교해야하기 때문에 O(N)의 시간복잡도를 갖는다.

- 반면 자료가 정렬되어 있는 경우 이진탐색을 통해 O(logN)의 시간복잡도로 값을 찾을 수 있다.

- 이진탐색은 범위를 주면 해당 범위 중간값을 기준으로 찾고자 하는 값이 중간값보다 큰지 작은지를 판단하는 방법이다.

- ex) 책에서 원하는 페이지 번호를 찾으려 할 때 일단 책을 펴고 찾고자 하는 페이지 번호가 더 작으면 앞부분을,

       찾고자 하는 페이지 번호가 더 크면 뒷부분을 보는 것과 같다.

2. 이진탐색 알고리즘

- 찾고자 하는 값을 target이라 한다

- 리스트 nums가 주어지면 가장 작은 인덱스를 left, 가장 큰 인덱스를 right라 하여 범위를 지정한다.

- left와 right의 중간 인덱스를 mid라 하고 nums[mid]와 target과 비교한다.

- nums[mid]가 target보다 크다면 left = mid + 1 ~ right 까지 범위에서 이진탐색을 다시 시행한다.

- nums[mid]가 target보다 작다면 left ~ right = mid - 1 까지 범위에서 이진탐색을 다시 시행한다.

- target을 발견했다면 해당하는 인덱스를 반환한다.

- target을 발견하지 못했다면 -1을 반환한다.

 

2 - 1) 이진탐색을 성공하는 경우

위와 같이 nums와 target이 주어졌다

left는 0, right는 7, mid는 3이 된다

target인 22보다 nums[mid]가 작으므로 left = mid + 1인 범위부터 다시 탐색한다

left는 4, right는 그대로 7, mid는 5가 된다

앞에서부터 차례대로 탐색하는 순차탐색의 경우 6번 비교해서 찾을 것을 2번만에 찾을 수 있게 된다

한 번 탐색할 때마다 탐색할 범위가 절반씩 사라지므로 자료의 개수가 커져도 연산 횟수가 크게 늘어나지 않는다(O(logN) 시간복잡도)

 

2 - 2) 이진탐색을 실패하는 경우

리스트에 없는 원소 4가 주어졌다

left는 0, right는 7, mid는 3이 된다

left는 그대로 0, right는 2, mid는 1이 된다

left, right, mid 모두 2가 된다

right는 그대로, left는 3, mid는 2가 된다

left의 값이 right의 값보다 커지게 되고 탐색은 종료된다

 

3. Python 구현

3 - 1) 반복문을 사용

def BinarySearch(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

 

3 - 2) 재귀를 사용

def BinarySearch(nums, target):
    def _search(left, right):
        if left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                return _search(mid + 1, right)
            elif nums[mid] > target:
                return _search(left, mid - 1)
            else:
                return mid
        return -1
    return _search(0, len(nums) - 1)

- left와 right를 비교할 때 등호가 헷갈릴 수 있는데 이진탐색의 경우 같은 left와 right가 같아지는 경우도 비교를 해야하므로 등호를 넣어준다

 

3 - 3) bisect module

from bisect import bisect_left

def BinarySearch(nums, target):
    idx = bisect_left(nums, target)
    if idx < len(nums) and nums[idx] == target:
        return idx
    return -1

bisect 모듈의 bisect_left를 사용해 이진탐색을 수행할 수 있다.

bisect_left는 lower bound를 수행하는 함수이다.

nums와 target이 파라미터로 주어지면 nums 안에서 target 이상이되는 최솟값을 반환하는 함수이다.

nums 안에 target이 존재한다면 idx는 target의 인덱스가 되고 target이 존재하지 않는다면 target의 인덱스보다 큰 값이 idx에 저장된다. nums[idx]와 target을 비교하여 둘이 같은 경우만 idx를 반환하면 이진 탐색을 수행할 수 있다.

 

bisect_left와 bisect_right에 대해서는 다음에 같이 다뤄보려 한다.